Approaching the problem without DP


If we did not have the constraint to give the lexicographically smallest solution our solution would just consist of the friend whose strength is minimum since that will result in max hits. So we can start from here and then try to fulfil the constraint in the second part of our solution. Consider example
where strength = [8, 8, 6, 5, 4]
and Tushar’s capacity = 11
Friend with min strength is at index 4 and has strength=4
maxHits = 11/4 = 2
so we start with [4,4] //these are indices of min strength friend
we also calculate the extra capacity that we have after hitting Tushar with maxHits using minStrength. That will be remCapacity = capacity-(minStrength*maxHits) or capacity = capacity%minStrength;

Now to construct our solution, we know we wouldn’t want to consider any index > minIdx since that will result in a lexicographically bigger result.
Now at index i, we will see if we can use this index in our solution, this is possible only if the difference between current strength and minStrength could be accommodated in the extra remStrength we have and then we update the remStrength.

vector<int> Solution::solve(int capacity, vector<int> &strength) {
    auto it = min_element(strength.begin(), strength.end());
    int minStrength = *it;
    int minIdx = it-strength.begin();
    int maxHits = capacity/minStrength;
    int remStrength = capacity%minStrength;
    vector<int>res(maxHits, minIdx);
    int j=0;
    int i=0;
    while(remStrength>0 && i<minIdx && j<maxHits){
        int diff = strength[i]-minStrength;
            remStrength= remStrength-diff;
            res[j] = i;
    return res;


Great effort and good solution yaar.