HackerRank Game of Two Stacks problem solution

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.

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 ("%dn", 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 ("%dn", 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();
}