In this HackerRank Game of Two Stacks problem, we have two stacks with nonnegative integer values. where index 0 denotes the top of the stack. in each move, we need to remove one integer from the top of either stack a or stack b. after that we need to find the maximum possible integers we removed from the two stacks.

HackerRank Game of Two Stacks problem solution


Problem solution in Python programming.

def brute(a,b):
    ans = 0
    a = [0]+a
    b = [0]+b
    for i in range(len(a)):
        for j in range(len(b)):
            sa = sum(a[:i+1])
            sb = sum(b[:j+1])
            if sa+sb > x:
                break
            ans = max(ans, i+j)

    return ans

def solve(a,b):
    total = 0
    i = len(a)
    ans = i
    j = 1
    for i in range(len(a)):
        total += a[i]
        if total > x:
            ans = i
            break

    ans_total = x + 1
    total = sum(a[:i])
    while (total <= x and i > 0) or j < len(b):
        if total < x:
            total += b[j - 1]
            j += 1
        elif total > x:
            total -= a[i - 1]
            i -= 1
        else:
            total -= a[i - 1]
            i -= 1
            total += b[j - 1]
            j += 1

        if i < 1 and total > x:
            break
        ans = max(ans, i + j - 2)
        ans_total = min(total, ans_total)

    return ans if ans_total <= x else ans - 1

for _ in range(int(input())):
    n, m, x = map(int, input().split())
    a = [int(x) for x in input().split()]
    b = [int(x) for x in input().split()]
    _sum_a, _sum_b = sum(a), sum(b)
    if _sum_a + _sum_b <= x:
        print(n+m)
    elif n <= 200 and m <= 200:
        print(brute(a,b))
    else:
        ans = solve(a,b) if _sum_a < _sum_b else solve(b,a)
        print(ans)


Problem solution in Java Programming.

import java.util.*;

public class GameOfTwoStacks {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int g = in.nextInt();
        
        for(int a0 = 0; a0 < g; a0++){
            int n = in.nextInt();
            int m = in.nextInt();
            int x = in.nextInt();
            
            long[] a_sum = new long[n];
            a_sum[0] = in.nextLong();
            for(int a_i=1; a_i < n; a_i++){

                a_sum[a_i] = in.nextLong()+a_sum[a_i-1];
            }
            
            long[] b_sum = new long[m];
            b_sum[0] = in.nextLong();
            for(int b_i=1; b_i < m; b_i++){
                b_sum[b_i] = in.nextLong()+b_sum[b_i-1];
            }
            
            
            //game
            int ai = a_sum.length-1;
            int bi = 0;
            int max_score = 0;
            int score = 0;
            
            while(ai>=0&&a_sum[ai] > x)
                ai--;
            
            if(ai>=0)
                while(bi<b_sum.length&&a_sum[ai]+b_sum[bi]<=x)
                    bi++;
            else
                while(bi<b_sum.length&&b_sum[bi]<=x)
                    bi++; 
            
            for(ai = ai; ai >= -1; ai--)
            {
                if(ai>=0)
                {
                    while(bi<b_sum.length&&a_sum[ai]+b_sum[bi]<=x)
                        bi++;
                    score = ai+bi+1;
                }
                else
                {
                    while(bi<b_sum.length&&b_sum[bi]<=x)
                        bi++;
                    score = bi;
                }
                
                if(score>max_score)
                    max_score = score;
            }
            
            System.out.println(max_score);
        }
    }
}


Problem solution in C++ programming.

#include <cstdio>

using namespace std;
int g,i,j,k,n,m,x,s1,Max,nr,y,s[100004];
int main()
{
    scanf ("%d", &g);
    for (i=1;i<=g;i++)
    {
        scanf ("%d %d %d", &n, &m, &x);
        s[0]=0;
        Max=n;
        nr=n;
        for (j=1;j<=n;j++)
        {
            scanf ("%d", &y);
            if (s[j-1]<=x)
                s[j]=s[j-1]+y;
            else if (Max==n)
            {
                nr=j-2;
                Max=j-2;
            }
        }
        if (s[n]>x && Max==n)
        {
            Max=n-1;
            nr=n-1;
        }
        scanf ("%d", &y);
        if (y<=x && Max==0)
            Max=1;
        for (j=nr;j>=1;j--)
        {
            if ((s[j]+y)<=x)
            {
                if ((j+1)>Max)
                    Max=j+1;
                break;
            }
            nr--;
        }
        s1=y;
        for (j=1;j<=(m-1);j++)
        {
            scanf ("%d", &y);
            if (s1<=x)
            {
                s1+=y;
                if (((j+1)>Max) && (s1<=x))
                    Max=j+1;
                for (k=nr;k>=1;k--)
                {
                    if ((s[k]+s1)<=x)
                    {
                        if ((j+k+1)>Max)
                            Max=j+k+1;
                        break;
                    }
                    nr--;
                }
            }
        }
        printf ("%d\n", Max);
    }
    return 0;
}


Problem solution in C programming.

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    int g; 
    scanf("%d",&g);
    for(int a0 = 0; a0 < g; a0++){
        int n; 
        int m; 
        int x; 
        scanf("%d %d %d",&n,&m,&x);
        int *a = malloc(sizeof(int) * n);
        for(int a_i = 0; a_i < n; a_i++){
           scanf("%d",&a[a_i]);
        }
        int *b = malloc(sizeof(int) * m);
        for(int b_i = 0; b_i < m; b_i++){
           scanf("%d",&b[b_i]);
        }
        // your code goes here
        int max = 0;
        int sum = 0;
        int items = 0;
        int apos = 0, bpos = 0;
        while (sum <= x && apos < n) {
            if (sum + a[apos] > x)
                break;
            sum += a[apos];
            apos++;
            items++;
        }
        while (sum <= x && bpos < m) {
            if (sum + b[bpos] > x)
                break;
            sum += b[bpos];
            bpos++;
            items++;
        }
        max = items;
        while (1) {
            if (apos <= 0)
                break;
            apos--;
            sum -= a[apos];
            items--;
            while (sum <= x && bpos < m) {
                if (sum + b[bpos] > x)
                    break;
                sum += b[bpos];
                bpos++;
                items++;
            }
            if (items > max)
                max = items;
            if (bpos == m)
                break;
        }
        printf ("%d\n", max);
    }
    return 0;
}


Problem solution in JavaScript programming.

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the twoStacks function below.
 */
function twoStacks(x, a, b) {
    var ai = 0, bi = 0;
    var ret = 0, total = 0, cnt = 0;
    while (ai < a.length && total + a[ai] <= x) {
        total += a[ai++];
    }
    while (bi < b.length && total + b[bi] <= x) {
        total += b[bi++];
    }
    ret = ai + bi;
    while (true) {
        while (ai > 0 && total + b[bi] > x) {
            total -= a[ai-1];
            ai--;
        }
        if (total + b[bi] > x || bi >= b.length) break;
        total += b[bi++];
        ret = Math.max(ret, ai + bi);
    }
    return ret;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const g = parseInt(readLine(), 10);

    for (let gItr = 0; gItr < g; gItr++) {
        const nmx = readLine().split(' ');

        const n = parseInt(nmx[0], 10);

        const m = parseInt(nmx[1], 10);

        const x = parseInt(nmx[2], 10);

        const a = readLine().split(' ').map(aTemp => parseInt(aTemp, 10));

        const b = readLine().split(' ').map(bTemp => parseInt(bTemp, 10));

        let result = twoStacks(x, a, b);

        ws.write(result + "\n");
    }

    ws.end();
}