Maximum equal sum stack

Easy

0/40

Average time to solve is 15m

Contributed by

10 upvotes

Asked in company

Problem statement

You are given three stacks of the positive numbers, your task is to find the possible equal maximum sum of the stacks with the removal of top elements allowed. Stacks are represented as an array, and the first index of the array represents the top element of the stack.

For example:

Assume that you are given three stacks {2,5}, {5,1,6} and {7,2,3,4}. Initially sum of stack one is 7, stack 2 is 12, and stack 3 is 16. But if we remove 5 from stack 2 that is top of stack its sum becomes 7. Similarly, if we remove 7 and then 2 from stack 3 then its sum also becomes 7 so the maximum possible sum for this case is 7.

Note :

1. If no such sum is possible return zero.

Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases.

The next 6 * T lines represent the ‘T’ test cases as follows-

The first line of each test case contains a single integer n1 which denotes the size of the first 

The second line of each test case contains space-separated integers that represent elements of the first stack and the starting element is the top of the stack. 

Similarly, the next 4 lines represent the other two stacks in the same manner.

Output format :

For each test case, print a single line containing a single integer denoting is the maximum possible equal sum for the three stacks.

The output of each test case will be printed in a separate line.

Note:

You don’t have to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 10000
1 <= DATA <= 10 ^ 6

Where ‘T’ is the total number of test cases, where N denotes the number of elements in any of the stacks and ‘DATA’ represents the data in the stacks.

Time limit: 1 sec.

Sample Input 1 :

Sample Output 1 :

5
15

Explanation of The Sample Input 1:

For the first test case:

The given stacks are {4,5,2,3}, {3,1,4}, {2,2,1} initially sum of individual stacks are 14, 8 and 5 but if we remove 4 and 5 from first stack and 3 from second stack then all the sum becomes equal, that is 5 therefore the answer will be 5.

For the second test case:

The given stacks are {4,9,6}, {1,4,5,5,5}, {15}. Initially, the sum of individual stacks are 19, 19 and 15 but if we remove 4 from the first stack and 1 and 4 from the second stack then the sum of individual stacks becomes equal, that is 15. Therefore, the answer will be 15.

Sample Input 2 :

Sample Output 2 :

3
0

Hint 1

Can we use three different pointers to keep track of the maximum equal sum?

Approaches (1)

Approach 1

Greedy

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

We will first calculate the sum of all three stacks one by one.
Then we will pop elements from the stack having the maximum sum and subtract or pop an element from this stack then check whether the sum of all the three stacks becomes equal or not.
Repeat the above step while we get the sum of all the three stacks equal.
If any of the stacks become empty while removing the element then we will just return zero else return the sum.

Time Complexity

O(N1 + N2 + N3), where ‘N1’, ‘N2’ and ‘N3’ denote the number of elements in the three stacks respectively.

Since the worst case can be that we have to pop every element from every stack and check so the net time complexity goes as O(N1) + O(N2) + O(N3) = O(N1 + N2 + N3).

Space Complexity

O(1).

Since we are a constant space.

(100% EXP penalty)

Maximum equal sum stack

Console