Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!
Stacks

Stack Challenge

Shaily

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:-

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

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

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

  4. 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));
    }
}



#include
using 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.

Leave a Reply

Your email address will not be published. Required fields are marked *

Close

Related Post