I'm trying to solve this hacker rank problem, which gives us two integer stacks and a maxSum variable assigned to a particular value and asks us to find total number of elements removed from top from both the stacks until sum of all number removed from stacks does not become greater than the given maxSum.

example;

stack 1 is; 4 2 4 6 1
stack 2 is; 2 1 8 5
maxSum=10
output=4 as we can remove 4,2,2, 1 & 4 2 2 1=9 which is less than 10.

I used below approach to implement my function to solve it and according to me everything in my code looks fine, but still i'm unable to pass many of the testcases. Kindly looking for help.

ps: i'm beginner in DSA.

int twoStacks(int maxSum, vector<int> a, vector<int> b) {
    int count=0;
    int sum=0;
    int i=0;
    int j=0;
    while(sum<=maxSum){
        if(i<a.size() && j<b.size() && sum min(a[i],b[j])<=maxSum){
            sum =min(a[i],b[j]);
            count  ;
            if(min(a[i],b[j])==a[i]){
                i  ;
            }
            else{
                j  ;
            }
        }
        else if(i>=a.size() && j<b.size() && sum b[j]<=maxSum){
            sum =b[j];
            count  ;
            j  ;
        }
        else if(i<a.size() && j>=b.size() && sum a[i]<=maxSum){
            sum =a[i];
            count  ;
            i  ;
        }
        else{
            break;
        }
    }
    return count;
}

CodePudding user response：

Start by taking elements from A until you reach or exceed the target.

Then, repeatedly remove elements from A until you fall short of the target, and add elements from B until you once again meet or exceed it.

Keep track of the largest excess.

Example Ruby code that passes all tests:

def twoStacks(max_sum, a, b)
    # curSum is the sum of the elements of `a` 
    # and `b` up to their indexes
    a_index = -1
    b_index = -1
    cur_sum = 0
    max_score = 0
    
    # Start with the initial, greedy score
    # found by taking successive elements of `a`
    # then `b` until we get to the max_sum
    while cur_sum <= max_sum 
        if a_index <= a.size - 2
            a_index  = 1
            cur_sum  = a[a_index]
        elsif b_index <= b.size - 2
            b_index  = 1 
            cur_sum  = b[b_index]
        else
            return a_index   b_index   2 if cur_sum <= max_sum
        end
        max_score = a_index   b_index   2 if cur_sum <= max_sum 
    end
        
    # Now we keep reducing `a_index` or increasing
    # `b_index` as needed to find the max score
    while true
        if cur_sum > max_sum
            return max_score if a_index < 0
            cur_sum -= a[a_index]
            a_index -= 1
        else
            b_index  = 1
            return max_score if b_index >= b.size
            cur_sum  = b[b_index]
        end
        max_score = [max_score, a_index   b_index   2].max if cur_sum <= max_sum
    end
end

CodePudding user response：

Your code assumes that there is a "greedy" approach to ensure you find the maximum possible number of removals. But this is not true. It is not always best to take the minimum value among the two stack tops. For example, stack B could start with a rather great value, but have many small values after it, which would make it interesting to still take that first great value and then profit from the many subsequent values you can take from it:

maxSum: 10
A: {5, 5, 5, 5}
B: {6, 1, 1, 1, 1, 1, 1}

Your algorithm would take twice from A, while it is better to take 5 times from B.

So first take as many as possible from A, and if you can take them all, also continue taking as many from B. This represents one possible solution.

Then continue to take one less value from A and see if you then can take more from B. This again represents a potential solution. Continue this process until either no elements from A can be returned to it, or all values of B have been taken.

Among all potential solutions keep track of the most removals that could be done.

Code:

int twoStacks(int maxSum, vector<int> a, vector<int> b) {
    int i = 0;
    int j = 0;
    int maxTakes = 0;
    // Take as many as possible from A
    while (i < a.size() && maxSum >= a[i]) {
        maxSum -= a[i  ];
    }
    while (true) {
        // Take as many as possible from B
        while (j < b.size() && maxSum >= b[j]) {
            maxSum -= b[j  ];
        }
        maxTakes = max(maxTakes, i   j);
        if (i == 0 || j >= b.size()) return maxTakes;
        // Return one value back to A so to make room for more from B
        maxSum  = a[--i];
    }
    return maxTakes;
}