## Algorithm

Problem Name: Data Structures - Game of Two Stacks

In this HackerRank in Data Structures - Game of Two Stacks solutions

Alexa has two stacks of non-negative integers, stack a[n] and stack b[m] here 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 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 maxSum 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 maxSum for 9 games, find the maximum possible score Nick can achieve.

Example

a = [1,2,3,4,5]

b = [6,7,8,9]

The maximum number of values Nick can remove is 4. here are two sets of choices with this result.

1. Remove 1,2,3,4 from a with a sum of 10.
2. Remove 1,2,3 from a and 6 from b with a sum of 12.

Function Description
Complete the twoStacks function in the editor below.

twoStacks has the following parameters: - int maxSum: the maximum allowed sum
- int a[n]: the first stack
- int b[m]: the second stack

Returns
- int: the maximum number of selections Nick can make

Input Format

The first line contains an integer, 9 (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 n (the number of integers in stack a), m (the number of integers in stack b), and maxSum (the number that the sum of the integers removed from the two stacks cannot exceed).
2. The second line contains n pace-separated integers, the respective values of a[i].
3. The third line contains m space-separated integers, the respective values of b[i].

Constraints

• 1 <= g <= 50
• 1 <= n,m <= 10**5
• 0 <= a[i],b[i] <= 10**6
• 1 <= maxSum <= 10**6

• 1 <= n,m <= 100 for 50% of the maximum score.

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:

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.

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

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);
vector < string> split(const string &);

/*
* Complete the 'twoStacks' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
*  1. INTEGER maxSum
*  2. INTEGER_ARRAY a
*  3. INTEGER_ARRAY b
*/

int twoStacks(int x, vector<int> a, vector<int> b) {
int sum = 0,i=0,j=0,ii=a.size(),jj=b.size() , cnt=0;
while(i < ii && sum+a[i]<=x)
sum+=a[i++];
cnt = i;
while(i>=0 && j < jj)
{
sum+=b[j++];
while(sum>x && i>0)
sum-=a[--i];
if(sum<=x && (i+j>>cnt)
cnt = i+j;
}
return cnt;
}

int main()
{
ofstream fout(getenv("OUTPUT_PATH"));

string g_temp;
getline(cin, g_temp);

int g = stoi(ltrim(rtrim(g_temp)));

for (int g_itr = 0; g_itr  <  g; g_itr++) {
string first_multiple_input_temp;
getline(cin, first_multiple_input_temp);

vector < string> first_multiple_input = split(rtrim(first_multiple_input_temp));

int n = stoi(first_multiple_input[0]);

int m = stoi(first_multiple_input[1]);

int maxSum = stoi(first_multiple_input[2]);

string a_temp_temp;
getline(cin, a_temp_temp);

vector < string> a_temp = split(rtrim(a_temp_temp));

vector<int> a(n);

for (int i = 0; i  <  n; i++) {
int a_item = stoi(a_temp[i]);

a[i] = a_item;
}

string b_temp_temp;
getline(cin, b_temp_temp);

vector < string> b_temp = split(rtrim(b_temp_temp));

vector<int> b(m);

for (int i = 0; i  <  m; i++) {
int b_item = stoi(b_temp[i]);

b[i] = b_item;
}

int result = twoStacks(maxSum, a, b);

fout << result << "\n";
}

fout.close();

return 0;
}

string ltrim(const string &str) {
string s(str);

s.erase(
s.begin(),
find_if(s.begin(), s.end(), not1(ptr_fun < int, int>(isspace)))
);

return s;
}

string rtrim(const string &str) {
string s(str);

s.erase(
find_if(s.rbegin(), s.rend(), not1(ptr_fun < int, int>(isspace))).base(),
s.end()
);

return s;
}

vector < string> split(const string &str) {
vector<string> tokens;

string::size_type start = 0;
string::size_type end = 0;

while ((end = str.find(" ", start)) != string::npos) {
tokens.push_back(str.substr(start, end - start));

start = end + 1;
}

tokens.push_back(str.substr(start));

}

``````
Copy The Code &

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
import java.util.Scanner;

public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int g = sc.nextInt();
for (int tc = 0; tc  <  g; tc++) {
int n = sc.nextInt();
int m = sc.nextInt();
int x = sc.nextInt();

System.out.println(solve(a, b, x));
}

sc.close();
}

static int[] readArray(Scanner sc, int size) {
int[] result = new int[size];
for (int i = 0; i  <  result.length; i++) {
result[i] = sc.nextInt();
}
return result;
}

static int solve(int[] a, int[] b, int x) {
int lengthB = 0;
int sum = 0;
while (lengthB  <  b.length && sum + b[lengthB] <= x) {
sum += b[lengthB];
lengthB++;
}

int maxScore = lengthB;
for (int lengthA = 1; lengthA  < = a.length; lengthA++) {
sum += a[lengthA - 1];

while (sum > x && lengthB > 0) {
lengthB--;
sum -= b[lengthB];
}

if (sum > x) {
break;
}

maxScore = Math.max(maxScore, lengthA + lengthB);
}
return maxScore;
}
}
``````
Copy The Code &

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
#!/bin/python3

import sys

g = int(input().strip())
for a0 in range(g):
n,m,x = input().strip().split(' ')
n,m,x = [int(n),int(m),int(x)]
a = list(map(int, input().strip().split(' ')))
b = list(map(int, input().strip().split(' ')))

a = a[::-1]
b = b[::-1]

handy_stack = []
el_count = 0
total = 0

while len(a) > 0:
if total + a[-1] <= x:
temp = a.pop()
handy_stack.append(temp)
total += temp
el_count += 1
else:
break

total_b = 0
while len(b) > 0:
if total_b + b[-1] <= x:
if total + b[-1] <= x:
temp = b.pop()
total += temp
total_b += temp
el_count += 1
else:
temp = b.pop()
total = total - handy_stack.pop() + temp
total_b += temp
else:
break

print(el_count)
``````
Copy The Code &