Stack Challenge

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:

Refer the best online coding classes and 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 <stdio.h>
// 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<bits/stdc++.h>
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<<countTotalScore(A, B, a, b, x)<<endl;
    }
}
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<a;i++)
            A[i]=sc.nextInt();
          for(int i=0;i<b;i++)
            B[i]=sc.nextInt(); 

          int ans= countTotalScore(A, B, a, b, x);
          System.out.println(ans);
        }
    }
  }

Previous post Valuable Time
Next post Play With Brackets

Leave a Reply

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