Sum Of Three Stacks

Easy

0/40

Average time to solve is 10m

Contributed by

9 upvotes

Asked in company

Problem statement

You are given three stacks A, B and C of positive integers with lengths 'lenA', 'lenB' and 'lenC' respectively.

Stacks are represented as an array in the input, and the first index of the array represents the topmost element of the stack.

You can remove any number of elements(possibly zero) from the top of each of the three stacks. Your task is to find the maximum possible equal sum of the elements of the stack.

For example-

Let the stacks be-
A = [2 , 2, 1, 1]
B = [1, 4]
C = [4]

We can remove the topmost element from stack A and the topmost element from stack B.

The final stacks after removal of the elements are-
A = [2, 1, 1]
B = [4]
C = [4]
Sum of elements of stack A = 4.
Sum of elements of stack B = 4.
Sum of elements of stack C = 4.

The maximum possible equal sum is equal to 4.

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

Input Format

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

Then the first line of each test case contains three space separated positive integers ‘len1’, ‘len2’ and ‘len3’ denoting the length of the stacks.

The second line of each test case contains lenA space separated positive integers the elements of stack A.

The third line of each test case contains lenB space separated positive integers the elements of stack B.

The third line of each test case contains lenC space separated positive integers the elements of stack C.

Output Format :

For each test case, Print the maximum possible equal sum after the removal of some top elements from each of the stack.

Output for each test case will be printed in a new line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= lenA, lenB, lenC <= 5000
1 <= A[i], B[i], C[i] <= 10^5

 Time Limit: 1sec

Sample Input 1 :

Sample Output 1:

3
3

Explanation for Sample 1:

For the first test case:
• We can remove the topmost 2 elements from stack B and the topmost 4 elements from stack C to get the maximum equal sum as 3.  

For the second test case:
• We can remove the topmost 2 elements from stack A to get the maximum equal sum as 3.

Sample Input 2:

Sample Output 2:

Hint 1

Can we use a greedy approach solution to solve this problem?

Approaches (1)

Approach 1

Greedy Approach

The key observation here is to compare the sum of each stack and if they are not the same, we remove the top element from the stack having the maximum sum.

The algorithm will be-

We find the sum of elements of the individual stack using one iteration for each of the stacks. Let the sums be ‘sum1’, ‘sum2’ and ‘sum3’ for A, B and C respectively.
Then, while(sum1 != sum2 or sum1 != sum3):
- We remove the topmost element of the stack having a maximum sum at the moment.
- If at any point, the size of any of the stack becomes 0 we return 0.
We finally return sum1.

Time Complexity

O(len1 + len2 + len3), where len1 denotes the size of stack A, len2 denotes the size of stack B and len3 denotes the size of stack C.

As every element of the stack will be visited at most twice, the time complexity will be linear.

Space Complexity

O(1), constant space is used.

(100% EXP penalty)

Sum Of Three Stacks

Console