Greedy: Given three stacks, you need to find maximum equal sum

Problem Statement:

You are given 3 stacks s1, s2, s3.

You need to find the maximum possible equal sum that can be achieved by removing from the top of the stack.

The final sum of the remaining elements in all three stacks must be the same.

Example:

Input: 

s1 = [4, 3, 1, 1, 1, 3]

s2 = [4, 3, 3]

s3 = [1, 4, 2, 2, 2]

Output: 6

Explanation: 

Remove 4, 3 from S1 to make the sum as 6
Remove 4 from S2 to make the sum as 6
Remove 1, 4 from S3 to make the sum as 6

Solution Explanation:

We will use greedy approach to solve the problem.

Initially calculate sum of all the stack and check if the sum are same.

If they are not same, then remove the top element from the stack having maximum sum.

Then again repeat the steps.

Time Complexity: O(n1+n2+n3)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>

using namespace std;

int solution(vector<int>& s1, vector<int>& s2, vector<int>& s3) 
{
    int sum1 = 0, sum2 = 0, sum3 = 0;

    for (int i = 0; i < s1.size(); i++)
        sum1 += s1[i];

    for (int i = 0; i < s2.size(); i++)
        sum2 += s2[i];

    for (int i = 0; i < s3.size(); i++)
        sum3 += s3[i];

    int top1 = 0, top2 = 0, top3 = 0;

    while (true) {
        if (top1 == s1.size() || top2 == s2.size() || top3 == s3.size())
            return 0;

        if (sum1 == sum2 && sum2 == sum3)
            return sum1;

        if (sum1 >= sum2 && sum1 >= sum3)
            sum1 -= s1[top1++];
        else if (sum2 >= sum1 && sum2 >= sum3)
            sum2 -= s2[top2++];
        else
            sum3 -= s3[top3++];
    }
}

int main() 
{
    vector<int> s1 = {4, 3, 1, 1, 1, 3};
    vector<int> s2 = {4, 3, 3};
    vector<int> s3 = {1, 4, 2, 2, 2};

    cout << solution(s1, s2, s3) << endl;
    return 0;
}

Output

6