Game of Two Stacks Hackerrank Problem Solution

Alexa has two stacks of non-negative integers, stack A=[a0,a1,…….am-1] and stack B=[b0,b1,…………bn-1where index 0 denotes the top of the stack. Alexa challenges Nick to play the following game Game of Two Stacks Hackerrank :

  • 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 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.

Given A, B, and x for g games, 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.

Input Format for Game of Two Stacks Hackerrank

The first line contains an integer, g (the number of games). The  3.g subsequent lines describe each game in the following format:

  1. The first line contains three space-separated integers describing the respective values of m (the number of integers in stack A), n (the number of integers in stack B), and x (the number that the sum of the integers removed from the two stacks cannot exceed).
  2. The second line contains m space-separated integers describing the respective values of  a0,a1,…………a-m-1
  3. The third line contains n space-separated integers describing the respective values of  b0,b1,…………bn-1.

Game of Two Stacks Hackerrank

Sample Input 0

1
5 4 10
4 2 4 6 1
2 1 8 5

Sample Output 0

4

Explanation 0

The two stacks initially look like this:

Game of Two Stacks Hackerrank

The image below depicts the integers Nick should choose to remove from the stacks. We print 4 as our answer because that is the maximum number of integers that can be removed from the two stacks without the sum exceeding x=10.

Game of Two Stacks Hackerrank

(There can be multiple ways to remove the integers from the stack, the image shows just one of them.)

Solution

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 were taken from A and it’s not possible to take any more integers from B.

C++

// vkreddy21  thanks to you.

#include <bits/stdc++.h>

using namespace std;

int main(){ 
    int g;
    cin >> g;    
    for(int a0 = 0; a0 < g; a0++){
        int n;
        int m;
        int x;
        cin >> n >> m >> x;
        
        vector<int> a(n);
        for(int a_i = 0; a_i <n; a_i++){
           cin >> a[a_i];
        }
        
        vector<int> b(m);
        for(int b_i =0; b_i <m; b_i++){
           cin >> b[b_i];
        }
        
        int sum=0,count=0,temp=0,i=0,j=0;        
        
        while(i<n && sum+a[i]<=x){    //considering only first stack and calculating count
            sum+=a[i];
            i++;
        }
        count=i;        
       
        while(j<m && i>=0){          //now adding one element of second stack at a time and subtracting the top element of first stack and calculating the count   
            sum+=b[j];             
            j++;
            while(sum>x && i>0){
                i--;
                sum-=a[i];
            }
            if(sum<=x && i+j>count)
                count=i+j;
        }
        cout<<count<<endl;
    } 
    return 0;
}

C

#include <bits/stdc++.h>

using namespace std;

int A[100002],B[100002];

int main(){
    int t;
    cin >> t;
    while (t--) {
        int n, m ,ms;
        scanf("%d%d%d", &n, &m, &ms);
 
        for(int A_i = 0; A_i < n; A_i++){
            scanf("%d",&A[A_i]);
        }
        for(int B_i = 0; B_i < m; B_i++){
           scanf("%d",&B[B_i]);
        }

        long long sum = 0;
        int x = 0, y = 0;

        while (x < n && sum + A[x] <= ms) {
            sum += A[x++];
        }

        int ans = x;

        while (y < m && x >= 0) {
            sum += B[y++];
            while (sum > ms && x > 0) {
                sum -= A[--x];
            }

            if (sum <= ms && ans < x + y) {
                ans = x + y;
            }
        }

        printf("%d\n",ans);
    }
    return 0;
}

 

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.