{"id":1476,"date":"2020-06-11T05:01:59","date_gmt":"2020-06-11T05:01:59","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1476"},"modified":"2022-03-30T22:05:10","modified_gmt":"2022-03-30T22:05:10","slug":"stack-sum","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/stack-sum\/","title":{"rendered":"STACK SUM"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645768393942-Article_494.png\" alt=\"\" \/><\/p>\n<h3>CONCEPTS USED:<\/h3>\n<blockquote>\n<p>Greedy algorithm.<\/p>\n<\/blockquote>\n<h3>DIFFICULTY LEVEL:<\/h3>\n<blockquote>\n<p>Medium.<\/p>\n<\/blockquote>\n<h3>PROBLEM STATEMENT<code>(<\/code>SIMPLIFIED<code>)<\/code>:<\/h3>\n<blockquote>\n<p>You are given three stacks containing positive numbers. Let<br \/>\nS1 be the sum of elements present in stack-1, S2 be the sum of elements present in stack-2, S3 be the sum of elements present in stack-3. The task is to make S1=S2=S3 and it should be as maximum as possible. The only operation allowed is the removal of top elements from the stacks. <\/p>\n<\/blockquote>\n<p><a href=\"https:\/\/mycode.prepbytes.com\/problems\/greedy-algo\/STKSUM\" title=\"Go to mycode.prepbytes.com\" target=\"_blank\" rel=\"noopener noreferrer\"><u><strong><\/strong><\/u><\/a><\/p>\n<h4>For Example :<\/h4>\n<pre><code>3 4 5\n3 4 1\n5 4 3 2\n6 4 7 3 2\n\n5\n\nRemove 3 from stack-1.Remove 5 and 4 from stack-2.\nRemove 6, 4, 7 from stack-3.\nRemaining element will add to 5 in all 3 stacks and it is the maximum possible.<\/code><\/pre>\n<h3>OBSERVATION:<\/h3>\n<blockquote>\n<p>The idea is to compare the sum of each stack, if they are not same, remove the top element of the stack having the maximum sum.<\/p>\n<\/blockquote>\n<h3>SOLVING APPROACH:<\/h3>\n<blockquote>\n<p>To solve this, we will follow this idea. The idea is to compare the sum of each stack, if they are not equal, then remove the top element of the stack having the maximum sum. <\/p>\n<p>We will follow these steps \u2212<\/p>\n<ol>\n<li>\n<p>Find sum of all elements of in each stack.<\/p>\n<\/li>\n<li>\n<p>If the sum of all three stacks is equal, then this is the maximum sum.<\/p>\n<\/li>\n<li>\n<p>Otherwise remove the top element of the stack having the maximum sum among three of stacks. Then repeat step 1 and step 2.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n<p><strong>Time Complexity<\/strong> : O(n + m + x) where n, m and x are sizes of three stacks.<\/p>\n<h3>SOLUTIONS:<\/h3>\n<p>\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_1477 {\r\n\toverflow:hidden;\r\n\tdisplay:block;\r\n\twidth:100%;\r\n\tborder:0px solid #ddd;\r\n\tmargin-bottom:30px;\r\n\t}\r\n\r\n#tab_container_1477 .tab-content{\r\n\tpadding:20px;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n\tmargin-top: 0px;\r\n\tbackground-color:#ffffff !important;\r\n\tcolor: #000000 !important;\r\n\tfont-size:16px !important;\r\n\tfont-family: Open Sans !important;\r\n\t\r\n\t\tborder: 1px solid #e6e6e6 !important;\r\n\t}\r\n#tab_container_1477 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_1477 .wpsm_nav-tabs > li.active > a, #tab_container_1477 .wpsm_nav-tabs > li.active > a:hover, #tab_container_1477 .wpsm_nav-tabs > li.active > a:focus {\r\n\tcolor: #000000 !important;\r\n\tcursor: default;\r\n\tbackground-color: #ffffff !important;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n}\r\n\r\n#tab_container_1477 .wpsm_nav-tabs > li > a {\r\n    margin-right: 0px !important; \r\n    line-height: 1.42857143 !important;\r\n    border: 1px solid #d5d5d5 !important;\r\n    border-radius: 0px 0px 0 0 !important; \r\n\tbackground-color: #e8e8e8 !important;\r\n\tcolor: #000000 !important;\r\n\tpadding: 15px 18px 15px 18px !important;\r\n\ttext-decoration: none !important;\r\n\tfont-size: 14px !important;\r\n\ttext-align:center !important;\r\n\tfont-family: Open Sans !important;\r\n}\r\n#tab_container_1477 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_1477 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_1477 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_1477 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_1477 .wpsm_nav-tabs > li > a:hover , #tab_container_1477 .wpsm_nav-tabs > li > a:focus {\r\n    color: #000000 !important;\r\n    background-color: #e8e8e8 !important;\r\n\tborder: 1px solid #d5d5d5 !important;\r\n\t\r\n}\r\n#tab_container_1477 .wpsm_nav-tabs > li > a .fa{\r\n\r\nmargin-right:5px !important;\r\n\r\nmargin-left:5px !important;\r\n\r\n\r\n}\r\n\r\n\t\t#tab_container_1477 .wpsm_nav-tabs a{\r\n\t\t\tbackground-image: none;\r\n\t\t\tbackground-position: 0 0;\r\n\t\t\tbackground-repeat: repeat-x;\r\n\t\t}\r\n\t\t\t\r\n\r\n\r\n#tab_container_1477 .wpsm_nav-tabs > li {\r\n    float: left;\r\n    margin-bottom: -1px !important;\r\n\tmargin-right:0px !important; \r\n}\r\n\r\n\r\n#tab_container_1477 .tab-content{\r\noverflow:hidden !important;\r\n}\r\n\r\n\r\n@media (min-width: 769px) {\r\n\r\n\t#tab_container_1477 .wpsm_nav-tabs > li{\r\n\t\tfloat:left !important ;\r\n\t\t\t\tmargin-right:-1px !important;\r\n\t\t\t\t\t}\r\n\t#tab_container_1477 .wpsm_nav-tabs{\r\n\t\tfloat:none !important;\r\n\t\tmargin:0px !important;\r\n\t}\r\n\r\n\t#tab_container_1477 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_1477 .wpsm_nav{\r\n\t\t\t}\r\n\r\n}\r\n\r\n\r\n\r\n@media (max-width: 768px) {\r\n\t#tab_container_1477 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_1477 .wpsm_nav{\r\n\t\t\t}\r\n}\r\n\r\n\r\n\t.wpsm_nav-tabs li:before{\r\n\t\tdisplay:none !important;\r\n\t}\r\n\r\n\t@media (max-width: 768px) {\r\n\t\t\t\t\r\n\t\t\t\t.wpsm_nav-tabs{\r\n\t\t\tmargin-left:0px !important;\r\n\t\t\tmargin-right:0px !important; \r\n\t\t\t\r\n\t\t}\r\n\t\t\t\t#tab_container_1477 .wpsm_nav-tabs > li{\r\n\t\t\tfloat:none !important;\r\n\t\t}\r\n\t\t\t\r\n\t}\t\t\t\t<\/style>\r\n\t\t\t\t<div id=\"tab_container_1477\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_1477\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  class=\"active\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_1477_1\" aria-controls=\"tabs_desc_1477_1\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>C<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_1477_2\" aria-controls=\"tabs_desc_1477_2\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>C++<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_1477_3\" aria-controls=\"tabs_desc_1477_3\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-laptop\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>Java<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_1477_4\" aria-controls=\"tabs_desc_1477_4\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>Python<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\t\t\t\t <\/ul>\r\n\r\n\t\t\t\t\t  <!-- Tab panes -->\r\n\t\t\t\t\t  <div class=\"tab-content\" id=\"tab-content_1477\">\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane  in active \" id=\"tabs_desc_1477_1\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"c\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"c\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\n#include &lt;stdio.h&gt;\r\n\r\n    int maxSum(int stack1[], int stack2[], int stack3[],\r\n           int n1, int n2, int n3)\r\n    {\r\n    int sum1 = 0, sum2 = 0, sum3 = 0;\r\n    for (int i = 0; i &lt; n1; i++)\r\n        sum1 += stack1[i];\r\n    for (int i = 0; i &lt; n2; i++)\r\n        sum2 += stack2[i];\r\n    for (int i = 0; i &lt; n3; i++)\r\n        sum3 += stack3[i];\r\n    int top1 = 0, top2 = 0, top3 = 0;\r\n    int ans = 0;\r\n    while (1)\r\n    {\r\n        if (top1 == n1 || top2 == n2 || top3 == n3)\r\n            return 0;\r\n        if (sum1 == sum2 &amp;&amp; sum2 == sum3)\r\n            return sum1;\r\n        if (sum1 &gt;= sum2 &amp;&amp; sum1 &gt;= sum3)\r\n            sum1 -= stack1[top1++];\r\n        else if (sum2 &gt;= sum3 &amp;&amp; sum2 &gt;= sum1)\r\n            sum2 -= stack2[top2++];\r\n        else if (sum3 &gt;= sum2 &amp;&amp; sum3 &gt;= sum1)\r\n            sum3 -= stack3[top3++];\r\n    }\r\n    }\r\n    int main()\r\n    {\r\n    int n, m, x;\r\n    scanf(&quot;%d%d%d&quot;,&amp;n,&amp;m,&amp;x);\r\n    int stack1[n], stack2[m], stack3[x];\r\n    for (int i = 0; i &lt; n; i++)\r\n        scanf(&quot;%d&quot;,&amp;stack1[i]);\r\n    for (int i = 0; i &lt; m; i++)\r\n        scanf(&quot;%d&quot;,&amp;stack2[i]);\r\n    for (int i = 0; i &lt; x; i++)\r\n        scanf(&quot;%d&quot;,&amp;stack3[i]);\r\n    printf(&quot;%d&#92;n&quot;,maxSum(stack1, stack2, stack3, n, m, x) );\r\n    return 0;\r\n    }\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane \" id=\"tabs_desc_1477_2\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"cpp\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\n#include &lt;bits\/stdc++.h&gt;\r\n    using namespace std;\r\n    int maxSum(int stack1[], int stack2[], int stack3[],\r\n           int n1, int n2, int n3)\r\n    {\r\n    int sum1 = 0, sum2 = 0, sum3 = 0;\r\n    for (int i = 0; i &lt; n1; i++)\r\n        sum1 += stack1[i];\r\n    for (int i = 0; i &lt; n2; i++)\r\n        sum2 += stack2[i];\r\n    for (int i = 0; i &lt; n3; i++)\r\n        sum3 += stack3[i];\r\n    int top1 = 0, top2 = 0, top3 = 0;\r\n    int ans = 0;\r\n    while (1)\r\n    {\r\n        if (top1 == n1 || top2 == n2 || top3 == n3)\r\n            return 0;\r\n        if (sum1 == sum2 &amp;&amp; sum2 == sum3)\r\n            return sum1;\r\n        if (sum1 &gt;= sum2 &amp;&amp; sum1 &gt;= sum3)\r\n            sum1 -= stack1[top1++];\r\n        else if (sum2 &gt;= sum3 &amp;&amp; sum2 &gt;= sum1)\r\n            sum2 -= stack2[top2++];\r\n        else if (sum3 &gt;= sum2 &amp;&amp; sum3 &gt;= sum1)\r\n            sum3 -= stack3[top3++];\r\n    }\r\n    }\r\n    int main()\r\n    {\r\n    int n, m, x;\r\n    cin &gt;&gt; n &gt;&gt; m &gt;&gt; x;\r\n    int stack1[n], stack2[m], stack3[x];\r\n    for (int i = 0; i &lt; n; i++)\r\n        cin &gt;&gt; stack1[i];\r\n    for (int i = 0; i &lt; m; i++)\r\n        cin &gt;&gt; stack2[i];\r\n    for (int i = 0; i &lt; x; i++)\r\n        cin &gt;&gt; stack3[i];\r\n    cout &lt;&lt; maxSum(stack1, stack2, stack3, n, m, x) &lt;&lt; endl;\r\n    return 0;\r\n    }\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane \" id=\"tabs_desc_1477_3\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"java\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\nimport java.util.*;\r\n     import java.io.*;\r\n\r\n    class stack_sum {\r\n    public static int maxSum(int stack1[], int stack2[], \r\n                            int stack3[], int n1, int n2, \r\n                                               int n3) \r\n    { \r\n      int sum1 = 0, sum2 = 0, sum3 = 0;  \r\n      for (int i=0; i &lt; n1; i++) \r\n          sum1 += stack1[i];  \r\n      for (int i=0; i &lt; n2; i++) \r\n          sum2 += stack2[i];  \r\n      for (int i=0; i &lt; n3; i++) \r\n          sum3 += stack3[i]; \r\n      int top1 =0, top2 = 0, top3 = 0; \r\n      int ans = 0; \r\n      while (true) \r\n      { \r\n          if (top1 == n1 || top2 == n2 || top3 == n3) \r\n             return 0; \r\n          if (sum1 == sum2 &amp;&amp; sum2 == sum3) \r\n             return sum1; \r\n          if (sum1 &gt;= sum2 &amp;&amp; sum1 &gt;= sum3) \r\n             sum1 -= stack1[top1++]; \r\n          else if (sum2 &gt;= sum3 &amp;&amp; sum2 &gt;= sum3) \r\n             sum2 -= stack2[top2++]; \r\n          else if (sum3 &gt;= sum2 &amp;&amp; sum3 &gt;= sum1) \r\n             sum3 -= stack3[top3++]; \r\n       } \r\n    } \r\n    public static void main(String[] args)  \r\n    { \r\n      Scanner sc = new Scanner(System.in);\r\n            int n = sc.nextInt();\r\n            int m = sc.nextInt();\r\n            int x = sc.nextInt();\r\n            int st1[]=new int[n];\r\n            int st2[]=new int[m];\r\n            int st3[]=new int[x];\r\n            for(int i=0;i&lt;n;i++)\r\n            {\r\n                st1[i] = sc.nextInt();\r\n            }\r\n            for(int i=0;i&lt;m;i++)\r\n            {\r\n                st2[i] = sc.nextInt();\r\n            }\r\n            for(int i=0;i&lt;x;i++)\r\n            {\r\n                st3[i] = sc.nextInt();\r\n            }\r\n          System.out.println(maxSum(st1, st2,  \r\n                               st3, n, m, x)); \r\n    } \r\n    } \r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane \" id=\"tabs_desc_1477_4\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"Python\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"Python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\n# your code goes here\r\ndef maxSum(stack1, stack2, stack3, n1, n2, n3):\r\n\r\n\tsum1 = 0\r\n\tsum2 = 0\r\n\tsum3 = 0\r\n\r\n\tfor i in range(n1):\r\n\t\tsum1 += stack1[i]\r\n\r\n\tfor i in range(n2):\r\n\t\tsum2 += stack2[i]\r\n\r\n\tfor i in range(n3):\r\n\t\tsum3 += stack3[i]\r\n\r\n\ttop1 = 0\r\n\ttop2 = 0\r\n\ttop3 = 0\r\n\tans = 0\r\n\r\n\twhile (1):\r\n\r\n\t\tif (top1 == n1 or top2 == n2 or top3 == n3):\r\n\t\t\treturn 0\r\n\r\n\t\tif (sum1 == sum2 and sum2 == sum3):\r\n\t\t\treturn sum1\r\n\r\n\t\tif (sum1 &gt;= sum2 and sum1 &gt;= sum3):\r\n\t\t\tsum1 -= stack1[top1]\r\n\t\t\ttop1 += 1\r\n\r\n\t\telif (sum2 &gt;= sum3 and sum2 &gt;= sum1):\r\n\t\t\tsum2 -= stack2[top2]\r\n\t\t\ttop2 += 1\r\n\r\n\t\telif (sum3 &gt;= sum2 and sum3 &gt;= sum1):\r\n\t\t\tsum3 -= stack3[top3]\r\n\t\t\ttop3 += 1\r\n\r\nn, m, x = map(int,input().split())\r\nstack1 = list(map(int,input().split()))\r\nstack2 = list(map(int,input().split()))\r\nstack3 = list(map(int,input().split()))\r\n\r\nprint(maxSum(stack1, stack2, stack3, n, m, x))\r\n\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t <\/div>\r\n\t\t\t\t\t \r\n\t\t\t\t <\/div>\r\n <script>\r\n\t\tjQuery(function () {\r\n\t\t\tjQuery('#myTab_1477 a:first').tab('show')\r\n\t\t});\r\n\t\t\r\n\t\t\t\tjQuery(function(){\r\n\t\t\tvar b=\"fadeIn\";\r\n\t\t\tvar c;\r\n\t\t\tvar a;\r\n\t\t\td(jQuery(\"#myTab_1477 a\"),jQuery(\"#tab-content_1477\"));function d(e,f,g){\r\n\t\t\t\te.click(function(i){\r\n\t\t\t\t\ti.preventDefault();\r\n\t\t\t\t\tjQuery(this).tab(\"show\");\r\n\t\t\t\t\tvar h=jQuery(this).data(\"easein\");\r\n\t\t\t\t\tif(c){c.removeClass(a);}\r\n\t\t\t\t\tif(h){f.find(\"div.active\").addClass(\"animated \"+h);a=h;}\r\n\t\t\t\t\telse{if(g){f.find(\"div.active\").addClass(\"animated \"+g);a=g;}else{f.find(\"div.active\").addClass(\"animated \"+b);a=b;}}c=f.find(\"div.active\");\r\n\t\t\t\t});\r\n\t\t\t}\r\n\t\t});\r\n\t\t\r\n\r\n\t\tfunction do_resize(){\r\n\r\n\t\t\tvar width=jQuery( '.tab-content .tab-pane iframe' ).width();\r\n\t\t\tvar height=jQuery( '.tab-content .tab-pane iframe' ).height();\r\n\r\n\t\t\tvar toggleSize = true;\r\n\t\t\tjQuery('iframe').animate({\r\n\t\t\t    width: toggleSize ? width : 640,\r\n\t\t\t    height: toggleSize ? height : 360\r\n\t\t\t  }, 250);\r\n\r\n\t\t\t  toggleSize = !toggleSize;\r\n\t\t}\r\n\r\n\r\n\t<\/script>\r\n\t\t\t\t\r\n\t\t\t<br \/>\n[forminator_quiz id=&quot;1478&quot;]<\/p>\n<p>This article tried to discuss the concept of <strong>Greedy algorithm<\/strong>. Hope this blog helps you understand and solve the problem. To practice more problems on Greedy algorithm you can check out <a href=\"#\"><\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>CONCEPTS USED: Greedy algorithm. DIFFICULTY LEVEL: Medium. PROBLEM STATEMENT(SIMPLIFIED): You are given three stacks containing positive numbers. Let S1 be the sum of elements present in stack-1, S2 be the sum of elements present in stack-2, S3 be the sum of elements present in stack-3. The task is to make S1=S2=S3 and it should be [&hellip;]<\/p>\n","protected":false},"author":52,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[99],"tags":[103,65],"class_list":["post-1476","post","type-post","status-publish","format-standard","hentry","category-greedy-algo-interview-coding","tag-greedy-algorithm","tag-interview"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v25.8 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Greedy Algo Interview Coding | Stack Sum | Prepbytes<\/title>\n<meta name=\"description\" content=\"The Idea Is to Compare the Sum of Each Stack, If They Are Not Same, Remove the Top Element of the Stack Having the Maximum Sum. If the Sum of All Three Stacks Is Equal.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/prepbytes.com\/blog\/stack-sum\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Greedy Algo Interview Coding | Stack Sum | Prepbytes\" \/>\n<meta property=\"og:description\" content=\"The Idea Is to Compare the Sum of Each Stack, If They Are Not Same, Remove the Top Element of the Stack Having the Maximum Sum. If the Sum of All Three Stacks Is Equal.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/prepbytes.com\/blog\/stack-sum\/\" \/>\n<meta property=\"og:site_name\" content=\"PrepBytes Blog\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prepbytes0211\/\" \/>\n<meta property=\"article:published_time\" content=\"2020-06-11T05:01:59+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-03-30T22:05:10+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645768393942-Article_494.png\" \/>\n<meta name=\"author\" content=\"Prepbytes\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Prepbytes\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/prepbytes.com\/blog\/stack-sum\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/stack-sum\/\"},\"author\":{\"name\":\"Prepbytes\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\"},\"headline\":\"STACK SUM\",\"datePublished\":\"2020-06-11T05:01:59+00:00\",\"dateModified\":\"2022-03-30T22:05:10+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/stack-sum\/\"},\"wordCount\":248,\"commentCount\":0,\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/stack-sum\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645768393942-Article_494.png\",\"keywords\":[\"greedy algorithm\",\"interview\"],\"articleSection\":[\"Greedy Algo Interview Coding\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/prepbytes.com\/blog\/stack-sum\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/prepbytes.com\/blog\/stack-sum\/\",\"url\":\"https:\/\/prepbytes.com\/blog\/stack-sum\/\",\"name\":\"Greedy Algo Interview Coding | Stack Sum | Prepbytes\",\"isPartOf\":{\"@id\":\"http:\/\/43.205.93.38\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/stack-sum\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/stack-sum\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645768393942-Article_494.png\",\"datePublished\":\"2020-06-11T05:01:59+00:00\",\"dateModified\":\"2022-03-30T22:05:10+00:00\",\"description\":\"The Idea Is to Compare the Sum of Each Stack, If They Are Not Same, Remove the Top Element of the Stack Having the Maximum Sum. If the Sum of All Three Stacks Is Equal.\",\"breadcrumb\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/stack-sum\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/prepbytes.com\/blog\/stack-sum\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/prepbytes.com\/blog\/stack-sum\/#primaryimage\",\"url\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645768393942-Article_494.png\",\"contentUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645768393942-Article_494.png\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/prepbytes.com\/blog\/stack-sum\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"http:\/\/43.205.93.38\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Greedy Algo Interview Coding\",\"item\":\"https:\/\/prepbytes.com\/blog\/category\/greedy-algo-interview-coding\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"STACK SUM\"}]},{\"@type\":\"WebSite\",\"@id\":\"http:\/\/43.205.93.38\/#website\",\"url\":\"http:\/\/43.205.93.38\/\",\"name\":\"PrepBytes Blog\",\"description\":\"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING\",\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"http:\/\/43.205.93.38\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"http:\/\/43.205.93.38\/#organization\",\"name\":\"Prepbytes\",\"url\":\"http:\/\/43.205.93.38\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"contentUrl\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"width\":160,\"height\":160,\"caption\":\"Prepbytes\"},\"image\":{\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.facebook.com\/prepbytes0211\/\",\"https:\/\/www.instagram.com\/prepbytes\/\",\"https:\/\/www.linkedin.com\/company\/prepbytes\/\",\"https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA\"]},{\"@type\":\"Person\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\",\"name\":\"Prepbytes\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g\",\"caption\":\"Prepbytes\"},\"url\":\"https:\/\/prepbytes.com\/blog\/author\/gourav-jaincollegedekho-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Greedy Algo Interview Coding | Stack Sum | Prepbytes","description":"The Idea Is to Compare the Sum of Each Stack, If They Are Not Same, Remove the Top Element of the Stack Having the Maximum Sum. If the Sum of All Three Stacks Is Equal.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/prepbytes.com\/blog\/stack-sum\/","og_locale":"en_US","og_type":"article","og_title":"Greedy Algo Interview Coding | Stack Sum | Prepbytes","og_description":"The Idea Is to Compare the Sum of Each Stack, If They Are Not Same, Remove the Top Element of the Stack Having the Maximum Sum. If the Sum of All Three Stacks Is Equal.","og_url":"https:\/\/prepbytes.com\/blog\/stack-sum\/","og_site_name":"PrepBytes Blog","article_publisher":"https:\/\/www.facebook.com\/prepbytes0211\/","article_published_time":"2020-06-11T05:01:59+00:00","article_modified_time":"2022-03-30T22:05:10+00:00","og_image":[{"url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645768393942-Article_494.png","type":"","width":"","height":""}],"author":"Prepbytes","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Prepbytes","Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/prepbytes.com\/blog\/stack-sum\/#article","isPartOf":{"@id":"https:\/\/prepbytes.com\/blog\/stack-sum\/"},"author":{"name":"Prepbytes","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e"},"headline":"STACK SUM","datePublished":"2020-06-11T05:01:59+00:00","dateModified":"2022-03-30T22:05:10+00:00","mainEntityOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/stack-sum\/"},"wordCount":248,"commentCount":0,"publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/stack-sum\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645768393942-Article_494.png","keywords":["greedy algorithm","interview"],"articleSection":["Greedy Algo Interview Coding"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/prepbytes.com\/blog\/stack-sum\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/prepbytes.com\/blog\/stack-sum\/","url":"https:\/\/prepbytes.com\/blog\/stack-sum\/","name":"Greedy Algo Interview Coding | Stack Sum | Prepbytes","isPartOf":{"@id":"http:\/\/43.205.93.38\/#website"},"primaryImageOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/stack-sum\/#primaryimage"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/stack-sum\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645768393942-Article_494.png","datePublished":"2020-06-11T05:01:59+00:00","dateModified":"2022-03-30T22:05:10+00:00","description":"The Idea Is to Compare the Sum of Each Stack, If They Are Not Same, Remove the Top Element of the Stack Having the Maximum Sum. If the Sum of All Three Stacks Is Equal.","breadcrumb":{"@id":"https:\/\/prepbytes.com\/blog\/stack-sum\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/prepbytes.com\/blog\/stack-sum\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/prepbytes.com\/blog\/stack-sum\/#primaryimage","url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645768393942-Article_494.png","contentUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645768393942-Article_494.png"},{"@type":"BreadcrumbList","@id":"https:\/\/prepbytes.com\/blog\/stack-sum\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"http:\/\/43.205.93.38\/"},{"@type":"ListItem","position":2,"name":"Greedy Algo Interview Coding","item":"https:\/\/prepbytes.com\/blog\/category\/greedy-algo-interview-coding\/"},{"@type":"ListItem","position":3,"name":"STACK SUM"}]},{"@type":"WebSite","@id":"http:\/\/43.205.93.38\/#website","url":"http:\/\/43.205.93.38\/","name":"PrepBytes Blog","description":"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING","publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"http:\/\/43.205.93.38\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"http:\/\/43.205.93.38\/#organization","name":"Prepbytes","url":"http:\/\/43.205.93.38\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/","url":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","contentUrl":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","width":160,"height":160,"caption":"Prepbytes"},"image":{"@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/prepbytes0211\/","https:\/\/www.instagram.com\/prepbytes\/","https:\/\/www.linkedin.com\/company\/prepbytes\/","https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA"]},{"@type":"Person","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e","name":"Prepbytes","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g","caption":"Prepbytes"},"url":"https:\/\/prepbytes.com\/blog\/author\/gourav-jaincollegedekho-com\/"}]}},"_links":{"self":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/1476","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/users\/52"}],"replies":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/comments?post=1476"}],"version-history":[{"count":8,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/1476\/revisions"}],"predecessor-version":[{"id":8377,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/1476\/revisions\/8377"}],"wp:attachment":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/media?parent=1476"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/categories?post=1476"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/tags?post=1476"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}