মডিউল ১৫-৪ঃ Maximum Equal Stack Sum (CodingNinjas)

প্রবলেম লিংকঃ Maximum Equal Stack Sum

প্রবলেম স্টেটমেন্টঃ তিনটি স্ট্যাক দেওয়া থাকবে। এই তিনটি স্ট্যাকের সাম অর্থাৎ সবগুলো এলিমেন্ট এর যোগফল সমান করতে হবে। এক্ষেত্রে এই সামের ভেলু ম্যাক্সিমাম পসিবল হতে হবে। সল্যুশনঃ আমরা শুরুতেই তিনটি স্ট্যাকের সাম বের করে নিতে পারি। এক্ষেত্রে আমরা মডিউলে দেখেছিলাম সাম বের করতে হলে আমরা স্ট্যাকের ভেলুগুলো পপ করে অন্য একটি স্ট্যাকে রাখি এবং ভেলুগুলো যোগ করতে থাকি। যেহেতু এই প্রবলেম এর ক্ষেত্রে আমাদের বার বার সাম বের করতে হবে। তাই এখানে সাম বের করার এই প্রসেস ফলো করলে কমপ্লেক্স হয়ে যাবে। তাই আমরা একটি সিম্পল ফাংশন রাখতে পারি সাম বের করার। সেই ফাংশনে স্ট্যাক পপ করে করে আমরা সাম বের করব। এক্ষেত্রে ফাংশনে স্ট্যাক রেফারেন্স দিয়ে পাস করব না, তাই ফাংশনে স্ট্যাক পপ হয়ে খালি হয়ে গেলেও আমাদের মেইন ফাংশনে ( যে ফাংশনে মেইন লজিকাল পার্টটুকু করছি ) কোন ইফেক্ট পরবে না।

#include <bits/stdc++.h>
int getSum(stack<int> s)    // ফাংশনে স্ট্যাক রেফারেন্স দিয়ে পাস করছি না।
{
    int sum = 0;
    while (!s.empty())    // ফাংশনে স্ট্যাক পপ করে করে আমরা সাম বের করছি।
    {
        sum += s.top();
        s.pop();
    }
    return sum;
}
int maxSum(stack<int> &s1, stack<int> &s2, stack<int> &s3)
{
    int sum1 = getSum(s1);    // শুরুতেই তিনটি স্ট্যাকের সাম বের করে নিতে পারি
    int sum2 = getSum(s2);
    int sum3 = getSum(s3);
    while (true)
    {
        if (sum1 == sum2 && sum2 == sum3)  // যদি তিনটির সাম সমান হয়ে যায় তাহলে আমাদের কাজ শেষ। লুপ ব্রেক করে দিচ্ছি। 
            break;
        if (sum1 >= sum2 && sum1 >= sum3)   // আর যদি তিনটির সাম সমান না হয় এবং এক্ষেত্রে বের করছি কার সাম বড়। 
        {
            sum1 -= s1.top();          // সেই বড় সাম থেকে টপের ভেলু কমিয়ে দিচ্ছি এবং স্ট্যাক থেকে টপের ভেলু পপ করে দিচ্ছি। 
            s1.pop();
        }
        else if (sum2 >= sum1 && sum2 >= sum3)
        {
            sum2 -= s2.top(); 
            s2.pop();
        }
        else
        {
            sum3 -= s3.top();
            s3.pop();
        }
    }
    return sum1;    // লুপ শেষে তিনটি স্ট্যাকের সাম সমান। যেকোন একটি রিটার্ন করে দিচ্ছি আন্সার হিসেবে।
}