title: Correct Algorithm for Game of two stacks on HackerRank
body: <p>I just attempted a stack based problem on HackerRank </p>
  
  <p><a href="https://www.hackerrank.com/challenges/game-of-two-stacks" rel="noreferrer">https://www.hackerrank.com/challenges/game-of-two-stacks</a> </p>
  
  <p>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:</p>
  
  <p>In each move, Nick can remove one integer from the top of either stack A  or B stack.</p>
  
  <p>Nick keeps a running sum of the integers he removes from the two stacks.</p>
  
  <p>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.</p>
  
  <p>Nick's final score is the total number of integers he has removed from the two stacks.</p>
  
  <p>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.</p>
  
  <p>For each of the  games, print an integer on a new line denoting the maximum possible score Nick can achieve without being disqualified.</p>
  
  <pre><code>Sample Input 0
  
  1 -&gt; Number of games
  10 -&gt; sum should not exceed 10 
  4 2 4 6 1  -&gt; Stack A
  2 1 8 5 -&gt; Stack B
  
  Sample Output 
  
  4
  </code></pre>
  
  <p>Below is my code I tried the greedy approach by taking the minimum element from the top of the stack &amp; adding it to the sum. It works fine for some of the test cases but fails for rest like for the below input </p>
  
  <pre><code>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
  </code></pre>
  
  <p>My code is giving <code>5</code> but the correct solution is <code>6</code> the elements popped out in series are <code>19,9,8,11,17,1</code>
  First three elements from stack A &amp; then from Stack B. </p>
  
  <p>**</p>
  
  <blockquote>
    <p>I don't understand the algorithm It appears like DP to me can anyone
    help me with the approach/algorithm?</p>
  </blockquote>
  
  <p>**</p>
  
  <pre><code>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 &lt; 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&lt;Integer&gt; stackOne = new Stack&lt;Integer&gt;();
              Stack&lt;Integer&gt; stackTwo = new Stack&lt;Integer&gt;();
  
              String[] stOne = br.readLine().split(" ");
              String[] stTwo = br.readLine().split(" ");
  
              for (int k = numOfElementsStackOne - 1; k &gt;= 0; k--) {
                  stackOne.push(Integer.parseInt(stOne[k]));
              }
  
              for (int j = numOfElementsStackTwo - 1; j &gt;= 0; j--) {
                  stackTwo.push(Integer.parseInt(stTwo[j]));
              }
  
              while (sum &lt;= 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() &amp;&amp; !stackTwo.isEmpty()) {
                      pk1 = stackOne.peek();
                      pk2 = stackTwo.peek();
  
                      if (pk1 &lt;= pk2) {
                          sum = sum + stackOne.pop();
                          popCount++;
                      } else {
                          sum = sum + stackTwo.pop();
                          popCount++;
                      }
                  } else if(stackOne.isEmpty() &amp;&amp; stackTwo.isEmpty()){
                      break;
                  }
              }
  
              int score = (popCount&gt;0)?(popCount-1):0;
              System.out.println(score);
          }
      }
  }
  </code></pre>