Alexa has two stacks of non—negative integers, stack A = [a0,a1, . . . ,an_1] and stack B = [b0, b1, . . . ,bm_1] where index 0 denotes the top of the stack. Alexa challenges Nick to play the following game:
In each move, Nick can remove one integer from the top of either stack A or stack B. Nick keeps a running sum of the integers he removes from the two stacks. Nick is disqualified from the game if, at any point, his running sum becomes greater than some integer given at the beginning of the game. Nick's fine/score is the total number of integers he has removed from the two stacks. Given A, B, and m for g games, find the maximum possible score Nick can achieve (i.e., the maximum number of integers he can remove without being disqualified)
My solution(greedy approach):
- Pick(pop) the smallest element between the one present on top of the stack A and the other present on top of the stack B. Increment sum by the value of popped element and total(number of ints) by 1.
- Repeat 1 until either sum becomes greater than asked or one of the two stacks get empty.
- If one of the two stacks get empty then pop ints from the other stack until the current sum exceeds the asked limit.
This problem can be solved in linear time. We'll begin by taking as many integers as possible from stack A without exceeding the sum. Once we've done this we'll start taking integers from B, but whenever the sum becomes larger than the limit, we'll put integers back into stack A. Make sure to update the answer (the number of integers) as the traversal through stack B takes place. Break the loop when you have put back all integers that was taken from A and it's not possible to take any more integers from B.
Please explain where am I getting wrong and what is the intuition behind the editorial solution?