Correct Algorithm for Game of two stacks on HackerRank

Question

I just attempted a stack based problem on HackerRank

https://www.hackerrank.com/challenges/game-of-two-stacks

Alexa has two stacks of non-negative integers, stack A and stack B 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 B stack.

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 X given at the beginning of the game.

Nick's final score is the total number of integers he has removed from the two stacks.

find the maximum possible score Nick can achieve (i.e., the maximum number of integers he can remove without being disqualified) during each game and print it on a new line.

For each of the games, print an integer on a new line denoting the maximum possible score Nick can achieve without being disqualified.

Sample Input 0

1 -> Number of games
10 -> sum should not exceed 10 
4 2 4 6 1  -> Stack A
2 1 8 5 -> Stack B

Sample Output 

4

Below is my code I tried the greedy approach by taking the minimum element from the top of the stack & adding it to the sum. It works fine for some of the test cases but fails for rest like for the below input

1
67
19 9 8 13 1 7 18 0 19 19 10 5 15 19 0 0 16 12 5 10 - Stack A
11 17 1 18 14 12 9 18 14 3 4 13 4 12 6 5 12 16 5 11 16 8 16 3 7 8 3 3 0 1 13 4 10 7 14 - Stack B

My code is giving 5 but the correct solution is 6 the elements popped out in series are 19,9,8,11,17,1 First three elements from stack A & then from Stack B.

**

I don't understand the algorithm It appears like DP to me can anyone help me with the approach/algorithm?

**

public class Default {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int numOfGames = Integer.parseInt(br.readLine());
        for (int i = 0; i < numOfGames; i++) {
            String[] tmp = br.readLine().split(" ");
            int numOfElementsStackOne = Integer.parseInt(tmp[0]);
            int numOfElementsStackTwo = Integer.parseInt(tmp[1]);
            int limit = Integer.parseInt(tmp[2]);
            int sum = 0;
            int popCount = 0;

            Stack stackOne = new Stack();
            Stack stackTwo = new Stack();

            String[] stOne = br.readLine().split(" ");
            String[] stTwo = br.readLine().split(" ");

            for (int k = numOfElementsStackOne - 1; k >= 0; k--) {
                stackOne.push(Integer.parseInt(stOne[k]));
            }

            for (int j = numOfElementsStackTwo - 1; j >= 0; j--) {
                stackTwo.push(Integer.parseInt(stTwo[j]));
            }

            while (sum <= limit) {
                int pk1 = 0;
                int pk2 = 0;
                if (stackOne.isEmpty()) {
                    sum = sum + stackTwo.pop();
                    popCount++;
                } else if (stackTwo.isEmpty()) {
                    sum = sum + stackOne.pop();
                    popCount++;
                } 
                else if (!stackOne.isEmpty() && !stackTwo.isEmpty()) {
                    pk1 = stackOne.peek();
                    pk2 = stackTwo.peek();

                    if (pk1 <= pk2) {
                        sum = sum + stackOne.pop();
                        popCount++;
                    } else {
                        sum = sum + stackTwo.pop();
                        popCount++;
                    }
                } else if(stackOne.isEmpty() && stackTwo.isEmpty()){
                    break;
                }
            }

            int score = (popCount>0)?(popCount-1):0;
            System.out.println(score);
        }
    }
}

user_2192861 · Answer

I see that there exist a solution and you marked it as correct, but I have a simple solution

add all elements from stack one that satisfy condition <= x
every element you add push it on stack called elements_from_a
set counter to size of stack
try add elements from stack b if sum > x so remove last element you added you can get it from stack elements_from_a
increment bstack counter with each add , decrements from astack with each remove
compare sum of steps with count and adjust count return count

here is code sample for the solution :

def twoStacks(x, a, b):
sumx = 0
asteps = 0
bsteps = 0
elements = []
maxIndex = 0

while len(a) > 0 and sumx + a[0] <= x :
    nextvalue =  a.pop(0)
    sumx+=nextvalue
    asteps+=1
    elements.append(nextvalue)

maxIndex = asteps


while len(b) > 0 and len(elements) > 0:
    sumx += b.pop(0)
    bsteps+=1
    while sumx > x and len(elements) > 0 :
        lastValue = elements.pop()
        asteps-=1
        sumx -= lastValue



    if sumx <= x and bsteps + asteps > maxIndex :
        maxIndex = bsteps + asteps



return maxIndex

I hope this is more simple solution.

user_2951377 · Answer

void traversal(int &max, int x, std::vector &a, int pos_a,
           std::vector &b, int pos_b) {

  if (pos_a < a.size() and a[pos_a] <= x) {
    max = std::max(pos_a + pos_b + 1, max);
    traversal(max, x - a[pos_a], a, pos_a + 1, b, pos_b);
  }

  if (pos_b < b.size() and b[pos_b] <= x) {
    max = std::max(pos_a + pos_b + 1, max);
    traversal(max, x - b[pos_b], a, pos_a, b, pos_b + 1);
  }
}

int twoStacks(int x, std::vector &a, std::vector &b) {
  int max = 0;
  traversal(max, x, a, 0, b, 0);
  return max;
}

A recursion solution, easy to understand. This solution takes the 2 stacks as a directed graph and traversal it.

user_9276996 · Answer

The Accepted Answer is Wrong. It fails for the below test case as depicted in the image.

For the test case given, if maximum sum should not exceed 10. Then correct answer is 5. But if we follow the approach by Amer Qarabsa, the answer would be 3. We can follow Geeky coder approach.

Correct Algorithm for Game of two stacks on HackerRank

6 Answers