Last Updated on March 30, 2022 by Ria Pathak
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, 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 −
Find sum of all elements of in each stack.
If the sum of all three stacks is equal, then this is the maximum sum.
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));
}
}
# your code goes here def maxSum(stack1, stack2, stack3, n1, n2, n3): sum1 = 0 sum2 = 0 sum3 = 0 for i in range(n1): sum1 += stack1[i] for i in range(n2): sum2 += stack2[i] for i in range(n3): sum3 += stack3[i] top1 = 0 top2 = 0 top3 = 0 ans = 0 while (1): if (top1 == n1 or top2 == n2 or top3 == n3): return 0 if (sum1 == sum2 and sum2 == sum3): return sum1 if (sum1 >= sum2 and sum1 >= sum3): sum1 -= stack1[top1] top1 += 1 elif (sum2 >= sum3 and sum2 >= sum1): sum2 -= stack2[top2] top2 += 1 elif (sum3 >= sum2 and sum3 >= sum1): sum3 -= stack3[top3] top3 += 1 n, m, x = map(int,input().split()) stack1 = list(map(int,input().split())) stack2 = list(map(int,input().split())) stack3 = list(map(int,input().split())) print(maxSum(stack1, stack2, stack3, n, m, x))
[forminator_quiz id="1478"]
This article tried to discuss the concept of Greedy algorithm. Hope this blog helps you understand and solve the problem. To practice more problems on Greedy algorithm you can check out MYCODE | Competitive Programming.