CONCEPTS USED:

Greedy algorithm.

DIFFICULTY LEVEL:

Medium.

PROBLEM STATEMENT(SIMPLIFIED):

You are given three stacks containing positive numbers. Let
S1 be the sum of elements present in stack-1, S2 be the sum of elements present in stack-2, S3 be the sum of elements present in stack-3. The task is to make S1=S2=S3 and it should be as maximum as possible. The only operation allowed is the removal of top elements from the stacks.


See original problem statement here

For Example :

3 4 5
3 4 1
5 4 3 2
6 4 7 3 2

5

Remove 3 from stack-1.Remove 5 and 4 from stack-2.
Remove 6, 4, 7 from stack-3.
Remaining element will add to 5 in all 3 stacks and it is the maximum possible.

OBSERVATION:

The idea is to compare the sum of each stack, if they are not same, remove the top element of the stack having the maximum sum.


SOLVING APPROACH:

To solve this, go through some online coding courses and we will follow this idea The idea is to compare the sum of each stack, if they are not equal, then remove the top element of the stack having the maximum sum.

We will follow these steps −

  1. Find sum of all elements of in each stack.

  2. If the sum of all three stacks is equal, then this is the maximum sum.

  3. Otherwise remove the top element of the stack having the maximum sum among three of stacks. Then repeat step 1 and step 2.

Time Complexity : O(n + m + x) where n, m and x are sizes of three stacks.


SOLUTIONS:

#include <stdio.h>

    int maxSum(int stack1[], int stack2[], int stack3[],
           int n1, int n2, int n3)
    {
    int sum1 = 0, sum2 = 0, sum3 = 0;
    for (int i = 0; i < n1; i++)
        sum1 += stack1[i];
    for (int i = 0; i < n2; i++)
        sum2 += stack2[i];
    for (int i = 0; i < n3; i++)
        sum3 += stack3[i];
    int top1 = 0, top2 = 0, top3 = 0;
    int ans = 0;
    while (1)
    {
        if (top1 == n1 || top2 == n2 || top3 == n3)
            return 0;
        if (sum1 == sum2 && sum2 == sum3)
            return sum1;
        if (sum1 >= sum2 && sum1 >= sum3)
            sum1 -= stack1[top1++];
        else if (sum2 >= sum3 && sum2 >= sum1)
            sum2 -= stack2[top2++];
        else if (sum3 >= sum2 && sum3 >= sum1)
            sum3 -= stack3[top3++];
    }
    }
    int main()
    {
    int n, m, x;
    scanf("%d%d%d",&n,&m,&x);
    int stack1[n], stack2[m], stack3[x];
    for (int i = 0; i < n; i++)
        scanf("%d",&stack1[i]);
    for (int i = 0; i < m; i++)
        scanf("%d",&stack2[i]);
    for (int i = 0; i < x; i++)
        scanf("%d",&stack3[i]);
    printf("%d\n",maxSum(stack1, stack2, stack3, n, m, x) );
    return 0;
    }
#include <bits/stdc++.h>
    using namespace std;
    int maxSum(int stack1[], int stack2[], int stack3[],
           int n1, int n2, int n3)
    {
    int sum1 = 0, sum2 = 0, sum3 = 0;
    for (int i = 0; i < n1; i++)
        sum1 += stack1[i];
    for (int i = 0; i < n2; i++)
        sum2 += stack2[i];
    for (int i = 0; i < n3; i++)
        sum3 += stack3[i];
    int top1 = 0, top2 = 0, top3 = 0;
    int ans = 0;
    while (1)
    {
        if (top1 == n1 || top2 == n2 || top3 == n3)
            return 0;
        if (sum1 == sum2 && sum2 == sum3)
            return sum1;
        if (sum1 >= sum2 && sum1 >= sum3)
            sum1 -= stack1[top1++];
        else if (sum2 >= sum3 && sum2 >= sum1)
            sum2 -= stack2[top2++];
        else if (sum3 >= sum2 && sum3 >= sum1)
            sum3 -= stack3[top3++];
    }
    }
    int main()
    {
    int n, m, x;
    cin >> n >> m >> x;
    int stack1[n], stack2[m], stack3[x];
    for (int i = 0; i < n; i++)
        cin >> stack1[i];
    for (int i = 0; i < m; i++)
        cin >> stack2[i];
    for (int i = 0; i < x; i++)
        cin >> stack3[i];
    cout << maxSum(stack1, stack2, stack3, n, m, x) << endl;
    return 0;
    }
import java.util.*;
     import java.io.*;

    class stack_sum {
    public static int maxSum(int stack1[], int stack2[], 
                            int stack3[], int n1, int n2, 
                                               int n3) 
    { 
      int sum1 = 0, sum2 = 0, sum3 = 0;  
      for (int i=0; i < n1; i++) 
          sum1 += stack1[i];  
      for (int i=0; i < n2; i++) 
          sum2 += stack2[i];  
      for (int i=0; i < n3; i++) 
          sum3 += stack3[i]; 
      int top1 =0, top2 = 0, top3 = 0; 
      int ans = 0; 
      while (true) 
      { 
          if (top1 == n1 || top2 == n2 || top3 == n3) 
             return 0; 
          if (sum1 == sum2 && sum2 == sum3) 
             return sum1; 
          if (sum1 >= sum2 && sum1 >= sum3) 
             sum1 -= stack1[top1++]; 
          else if (sum2 >= sum3 && sum2 >= sum3) 
             sum2 -= stack2[top2++]; 
          else if (sum3 >= sum2 && sum3 >= sum1) 
             sum3 -= stack3[top3++]; 
       } 
    } 
    public static void main(String[] args)  
    { 
      Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int m = sc.nextInt();
            int x = sc.nextInt();
            int st1[]=new int[n];
            int st2[]=new int[m];
            int st3[]=new int[x];
            for(int i=0;i<n;i++)
            {
                st1[i] = sc.nextInt();
            }
            for(int i=0;i<m;i++)
            {
                st2[i] = sc.nextInt();
            }
            for(int i=0;i<x;i++)
            {
                st3[i] = sc.nextInt();
            }
          System.out.println(maxSum(st1, st2,  
                               st3, n, m, x)); 
    } 
    } 

Previous post Dedicate Length
Next post AMAN RELATIVES

Leave a Reply

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