Last Updated on May 11, 2022 by Ria Pathak

### Concepts Used

Stack

### Difficulty Level

Hard

### Problem Statement :

Rahul and Ritika are playing a game of stacks where each of them are having a stack A and B of integers. Rahul gives a random integer X to Ritika and tells her about the rules of the game which are:-

In each move, Ritika can remove one integer from the top of either stack A or stack B.

Ritika keeps a running sum of the integers she removes from the two stacks.

Ritika is disqualified from the game if, at any point, her running sum becomes greater than some integer X given at the beginning of the game.

Ritika’s final score is the total number of integers she has removed from the two stacks.

Find the maximum possible score Ritika can achieve during each game and print it.

**See original problem statement here**

#### Example:

```
Input
1
5 4 10
4 2 4 6 1
2 1 8 5
Output
4
Explanation
In the given test case
4, 2 from the first stack and 2, 1 from the second stack
can be removed to achieve a sum of 9 which is less than 10.
So, the total score of Ritika becomes 4.
```

### Explanation:

calculate the sum of all elements in the array A till the sum is less than or equal to x.

store the index of the last array traversed to mentain the total count.

now, traverse the second array to get the total sum and count the total number of possibilities.

if the sum becomes greater than x then, keep reducing the sum from first array till it becomes less than x.

if sum is less than or equal to x and value of index1 + index2 is greater than total count, then update the count.

return the total count.

### Using stack:

#include// Function to return the total count. int countTotalScore(int A[], int B[], int a, int b, int x){ int index1 = 0, index2 = 0; int sum = 0, count; // calculate the sum of all elements in the array A till the sum is less than or equal to x. while(index1 < a && sum + A[index1] <= x){ sum += A[index1]; index1++; } // store the index of the last array traversed to mentain the total count. count = index1; // now, traverse the second array to get the total sum and count the total number of possibilities. while(index2 < b && index1 >= 0){ sum += B[index2]; index2++; // if the sum becomes greater than x then, keep reducing the sum from first array till it becomes less than x. while(sum > x && index1 > 0){ index1--; sum -= A[index1]; } // if sum is less than or equal to x and value of index1 + index2 is greater than total count, then update the count. if(sum <= x && (index1 + index2) > count) count = (index1 + index2); } // return the total count. return count; } // Driver function to check the above algorithm. int main(){ int t; scanf("%d",&t); while(t--){ int a, b, x; scanf("%d%d%d",&a,&b,&x); int A[a], B[b]; for(int i = 0; i < a; i++) scanf("%d",&A[i]); for(int i = 0; i < b; i++) scanf("%d",&B[i]); printf("%d\n",countTotalScore(A, B, a, b, x)); } }

#includeusing namespace std; // Function to return the total count. int countTotalScore(int A[], int B[], int a, int b, int x){ int index1 = 0, index2 = 0; int sum = 0, count; // calculate the sum of all elements in the array A till the sum is less than or equal to x. while(index1 < a && sum + A[index1] <= x){ sum += A[index1]; index1++; } // store the index of the last array traversed to mentain the total count. count = index1; // now, traverse the second array to get the total sum and count the total number of possibilities. while(index2 < b && index1 >= 0){ sum += B[index2]; index2++; // if the sum becomes greater than x then, keep reducing the sum from first array till it becomes less than x. while(sum > x && index1 > 0){ index1--; sum -= A[index1]; } // if sum is less than or equal to x and value of index1 + index2 is greater than total count, then update the count. if(sum <= x && (index1 + index2) > count) count = (index1 + index2); } // return the total count. return count; } // Driver function to check the above algorithm. int main(){ int t; cin>>t; while(t--){ int a, b, x; cin>>a>>b>>x; int A[a], B[b]; for(int i = 0; i < a; i++) cin>>A[i]; for(int i = 0; i < b; i++) cin>>B[i]; cout<

import java.util.*; import java.io.*; public class Main { static int countTotalScore(int[] A, int B[], int a, int b, int x) { int index1 = 0, index2 = 0; int sum = 0, count; // calculate the sum of all elements in the array A //till the sum is less than or equal to x. while(index1 < a && sum + A[index1] <= x){ sum += A[index1]; index1++; } // store the index of the last array traversed to mentain the //total count. count = index1; // now, traverse the second array to get the total sum and //count the total number of possibilities. while(index2 < b && index1 >= 0){ sum += B[index2]; index2++; // if the sum becomes greater than x then, keep reducing //the sum from first array till it becomes less than x. while(sum > x && index1 > 0){ index1--; sum -= A[index1]; } // if sum is less than or equal to x and value of index1 + index2 //is greater than total count, then update the count. if(sum <= x && (index1 + index2) > count) count = (index1 + index2); } // return the total count. return count; } public static void main(String args[]) throws IOException { Scanner sc=new Scanner(System.in); int t=sc.nextInt(); while(t-- >0){ int a,b,x; a=sc.nextInt(); b=sc.nextInt(); x=sc.nextInt(); int[] A= new int[a]; int[] B= new int[b]; for(int i=0;i

def countTotalScore(A, B, a, b, x): index1 = 0 index2 = 0 sum = 0 while(index1 < a and sum + A[index1] <= x): sum += A[index1] index1 += 1 count = index1 while(index2 < b and index1 >= 0): sum += B[index2] index2 += 1 while(sum > x and index1 > 0): index1 -= 1 sum -= A[index1] if(sum <= x and (index1 + index2) > count): count = (index1 + index2) return count for _ in range(int(input())): a, b, x = map(int,input().split()) A = list(map(int,input().split())) B = list(map(int,input().split())) print(countTotalScore(A, B, a, b, x)) # your code goes here

[forminator_quiz id="2318"]

This article tried to discuss the concept of **stack**. Hope this blog helps you understand and solve the problem. To practice more problems on stack you can check out MYCODE | Competitive Programming.