finding maximum height of stack such that it is equal for all three stack

Question

we have three stacks of cylinders where each cylinder has the same diameter, but they may vary in height. we can change the height of a stack by removing and discarding its topmost cylinder any number of times.

Find the maximum possible height of the stacks such that all of the stacks are exactly the same height. This means you must remove zero or more cylinders from the top of zero or more of the three stacks until they are all the same height, then return the height.

example:

h1 = [3, 2, 1, 1, 1] //remove 3 , it will make height 5 i.e (1+1+1+2=5);

h2 = [4, 3, 2]       //remove [4] it will make height 5;

h3 = [1, 1, 4, 1]    //remove [1,1] it will make height 5;

It will return 5 as answer. my approach I counted sum1 for stack1 sum2 for stack2 and sum3 for stack 3 and then started decreasing the greatest sum value by subtracting it with the topmost element of that stack && popping it out then iteratively using while(sum1!=sum2 || sum2!=sum3 ||sum3!sum1). but my while loop executed successfully up to 2 conditional statements and after that, it kept processing without giving output, it appears it went infinite loop but I have included all conditions to terminate the loop. what goes wrong with my approach, please do help, thank you so much.

my code;

#include<iostream>
#include<stack>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
    vector<int>h1={3,2,1,1,1};
    vector<int>h2={4,3,2};
    vector<int>h3={1,1,4,1};
    int sum1=0,sum2=0,sum3=0;
    stack<int>s1,s2,s3;
    for(int i=h1.size()-1;i>=0;i--){
            s1.push(h1[i]);
            sum1+=h1[i];
        }
    for(int i=h2.size()-1;i>=0;i--){
            s2.push(h2[i]);
            sum2+=h2[i];
        }
    for(int i=h3.size()-1;i>=0;i--){
            s3.push(h3[i]);
            sum3+=h3[i];
        }
        while(sum1!=sum2 || sum2!=sum3 ||  sum3!=sum1){
        vector<int>sum;
        sum.push_back(sum1);sum.push_back(sum2);sum.push_back(sum3);
        sort(sum.begin(),sum.end(),greater<int>());
        if(sum1==sum[0] && sum2!=sum[0] && sum3!=sum[0] && !s1.empty()){
            sum1=sum1-s1.top();
            s1.pop();
            cout<<sum1<<endl;
            cout<<s1.top()<<endl;

        }
        if(sum2==sum[0] && sum3!=sum[0] && sum1!=sum[0] && !s2.empty() ){
            sum2=sum2-s2.top();
            s2.pop();
            cout<<sum2<<endl;
            cout<<s2.top()<<endl;
        }
        if (sum3==sum[0] && sum2!=sum[0] && sum3!=sum[0] && !s3.empty()){
            sum3=sum3-s3.top();
            s3.pop();
            cout<<sum3<<endl;
            cout<<s3.top();
            //h3.pop_back();
        }
        if (sum1==sum[0] && sum2==sum[0] && sum3!=sum[0] && !s1.empty() && !s2.empty()){
            sum1=sum1-s1.top();sum2=sum2-s2.top();
            s1.pop();s2.pop();
            //h1.pop_back();h2.pop_back();
        }
        if (sum1!=sum[0] && sum2==sum[0] && sum3==sum[0] && !s2.empty() && !s3.empty()){
            sum2=sum2-s2.top();sum3=sum3-s3.top();
            s2.pop();s3.pop();
            //h2.pop_back();h3.pop_back();
        }
        if (sum1==sum[0] && sum2!=sum[0] && sum3==sum[0]  && !s1.empty() && !s3.empty()){
            sum1=sum1-s1.top();sum3=sum3-s3.top();
            s1.pop();s3.pop();
            //h1.pop_back();h3.pop_back();
        }
    }
    cout<<"ans"<<sum1;
}

Answer 1

One approach is to use a max heap. If sum of top stack of the max heap is equal to the minimum of sums then its done.

Algorithm :

1. Compute the sum of elements in each stack and track the minimum.
2. Add each stack as a tuple like (index_of_the_stack, current_sum_of_the_stack) to a max heap with sum as the comparator.
3. If sum of top stack of the max heap is equal to minimum sum you are done.
4. Otherwise remove the max stack of the heap - by removing max stack I mean remove the tuple (index, sum)
5. Then keep removing elements from the stack with that index until its sum is less than or equal to the minimum sum.
6. Update the minimum sum as minimum_sum = min(minimum_sum, sum_of_updated_top_stack)
7. Add the tuple ( index, updated_sum_of_the_stack ) back to the heap.
8. Go to step 3.

This should handle any number of stacks.