{"id":1464,"date":"2020-06-11T04:51:11","date_gmt":"2020-06-11T04:51:11","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1464"},"modified":"2022-05-16T10:40:15","modified_gmt":"2022-05-16T10:40:15","slug":"remaining-gold-coin","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/","title":{"rendered":"REMAINING GOLD COIN"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645181869567-Article_470.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 have a bag full of Gold Coins. Each coin has a positive integer inscribed on it, that denotes the value of the gold coin. Now you start playing with those gold coins. In each turn you choose two largest value gold coints suppose v1 and v2 with v1 <\/p>\n<ol>\n<li>if v1 == v2, both the coins are removed from the bag.<\/li>\n<li>if v1 != v2, a new coin with value v2\u2212v1 is added into the bag.<br \/>\nThe game continues until there is only one coin left in the bag. The task is to print the value of the remaining gold coin.<\/li>\n<\/ol>\n<\/blockquote>\n<p><a href=\"https:\/\/mycode.prepbytes.com\/problems\/greedy-algo\/REMGLD\" 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>2\n6\n1 3 3 6 4 8\n5\n9 2 1 7 8\n\n1\n3\n\nIn the first test case\n1. 8\u22126=2, [1,2,3,3,4]\n2. 4\u22123=1, [1,1,2,3]\n3.3\u22122=1, [1,1,1]\n4. [1]\n\nIn the second test case\n1. 9-8=1,[1,1,2,7]\n2. 7-2=5 ,[1,1,5]\n3. 5-1=4 ,[1,4]\n4. 4-1=3 ,[3]<\/code><\/pre>\n<h3>OBSERVATION:<\/h3>\n<blockquote>\n<p>Since we need the two largest value coins at each iteration, priority queues are most suited.<\/p>\n<\/blockquote>\n<h3>SOLVING APPROACH:<\/h3>\n<blockquote>\n<p>Use a max-heap or a maximum priority queue to store all the elements.<\/p>\n<p>While the size of queue is greater than 1, extract the top two elements.<\/p>\n<p>If the two elements taken are equal, discard them.<\/p>\n<p>Else,push back their difference to the queue.<\/p>\n<p>The last element left in the queue is the answer.<\/p>\n<\/blockquote>\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_1465 {\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_1465 .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_1465 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_1465 .wpsm_nav-tabs > li.active > a, #tab_container_1465 .wpsm_nav-tabs > li.active > a:hover, #tab_container_1465 .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_1465 .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_1465 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_1465 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_1465 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_1465 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_1465 .wpsm_nav-tabs > li > a:hover , #tab_container_1465 .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_1465 .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_1465 .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_1465 .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_1465 .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_1465 .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_1465 .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_1465 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_1465 .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_1465 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_1465 .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_1465 .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_1465\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_1465\">\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_1465_1\" aria-controls=\"tabs_desc_1465_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_1465_2\" aria-controls=\"tabs_desc_1465_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_1465_3\" aria-controls=\"tabs_desc_1465_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-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>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\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_1465\">\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_1465_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    #include &lt;string.h&gt;\r\n     #include&lt;stdlib.h&gt;\r\n    int prio_queue[100005];int ind=-1;\r\n    void percolateup(int pos)\r\n    {\r\n    if(pos&lt;1)\r\n    return ;\r\n    int par=(pos-1)\/2;\r\n    if(prio_queue[par]&lt;prio_queue[pos])\r\n    {\r\n        int temp=prio_queue[par];\r\n        prio_queue[par]=prio_queue[pos];\r\n        prio_queue[pos]=temp;\r\n        percolateup(par);\r\n    }\r\n    }\r\n     void percolatedown(int pos)\r\n    {\r\n    int left=2*pos+1,right=2*pos+2,max=pos;\r\n    if(left&lt;=ind)\r\n    {\r\n        if(prio_queue[pos]&lt;prio_queue[left])\r\n        max=left;\r\n    }\r\n    if(right&lt;=ind)\r\n    {\r\n        if(prio_queue[max]&lt;prio_queue[right])\r\n        max=right;\r\n    }\r\n    if(pos!=max)\r\n    {\r\n        int temp=prio_queue[max];\r\n        prio_queue[max]=prio_queue[pos];\r\n        prio_queue[pos]=temp;\r\n        percolatedown(max);\r\n    }\r\n    }\r\n     void insert(int x)\r\n    {\r\n    prio_queue[++ind]=x;\r\n    percolateup(ind);\r\n    }\r\n     void del()\r\n    {\r\n    prio_queue[0]=prio_queue[ind];\r\n    ind--;\r\n    percolatedown(0);\r\n    }\r\n    int getmax()\r\n    {\r\n    if(ind==-1)\r\n    return -1;\r\n    return prio_queue[0];\r\n    }\r\n     int main()\r\n    {\r\n    int t;scanf(&quot;%d&quot;,&amp;t);\r\n    while(t--)\r\n    {\r\n        ind=-1;\r\n        int n;scanf(&quot;%d&quot;,&amp;n);\r\n        for(int i=0;i&lt;n;i++)\r\n        {\r\n            int x;scanf(&quot;%d&quot;,&amp;x);\r\n            insert(x);\r\n        }int x,y;\r\n        while(ind&gt;0)\r\n        {\r\n             x=getmax();\r\n            del();\r\n             y=getmax();\r\n\r\n            del();\r\n            \/\/printf(&quot;%d %d &quot;,x,y);\r\n            if(x!=y)\r\n            {\r\n                insert(abs(x-y));\r\n            }\r\n        }\r\n        if(ind==-1)\r\n        printf(&quot;0&#92;n&quot;);\r\n        else\r\n        printf(&quot;%d&#92;n&quot;,prio_queue[0]);\r\n    }\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_1465_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\r\n    int lastStoneWeight(vector&lt;int&gt; &amp;s)\r\n    {\r\n    priority_queue&lt;int&gt; q(begin(s), end(s));\r\n    while (q.size() &gt; 1)\r\n    {\r\n        auto y = q.top();\r\n        q.pop();\r\n        auto x = q.top();\r\n        q.pop();\r\n        if (x &lt; y)\r\n            q.push(y - x);\r\n    }\r\n\r\n    return !q.empty() ? q.top() : 0;\r\n    }\r\n    int main()\r\n    {\r\n    int t;\r\n    cin &gt;&gt; t;\r\n    while (t--)\r\n    {\r\n        int n;\r\n        cin &gt;&gt; n;\r\n        vector&lt;int&gt; arr;\r\n        int ele;\r\n        for (int i = 0; i &lt; n; i++)\r\n        {\r\n            cin &gt;&gt; ele;\r\n            arr.emplace_back(ele);\r\n        }\r\n        cout &lt;&lt; lastStoneWeight(arr) &lt;&lt; &quot;&#92;n&quot;;\r\n    }\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_1465_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    import java.util.PriorityQueue; \r\n\r\n    class gold\r\n     { \r\n    static int remgold(int arr[], int n) \r\n    { \r\n        int i, sum = 0; \r\n        PriorityQueue&lt;Integer&gt; pq =  \r\n             new PriorityQueue&lt;Integer&gt;(Collections.reverseOrder()); \r\n        for (i = 0; i &lt; n; i++) \r\n            pq.add(arr[i]); \r\n        while (pq.size() &gt; 1) \r\n        { int y = pq.poll();\r\n        int x = pq.poll();;\r\n        if (x &lt; y)\r\n            pq.add(y - x);\r\n        } \r\n        if(pq.size()==0)\r\n        return 0;\r\n        return pq.poll();\r\n    } \r\n    public static void main(String[] args) \r\n    { Scanner sc = new Scanner(System.in);\r\n        int t= sc.nextInt();\r\n        while(t-- &gt;0 ){\r\n            int n = sc.nextInt();\r\n            int arr[]=new int[n];\r\n            for(int i=0;i&lt;n;i++)\r\n            {\r\n                arr[i] = sc.nextInt();\r\n            }\r\n        System.out.println(remgold(arr, n)); }\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\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_1465 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_1465 a\"),jQuery(\"#tab-content_1465\"));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;1467&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 have a bag full of Gold Coins. Each coin has a positive integer inscribed on it, that denotes the value of the gold coin. Now you start playing with those gold coins. In each turn you choose two largest value gold coints suppose v1 and [&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-1464","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>Remaining Gold Coin | Greedy Algo Interview Coding | Prepbytes<\/title>\n<meta name=\"description\" content=\"You Have a Bag Full of Gold Coins. Each Coin Has a Positive Integer Inscribed on It. in Each Turn You Choose Two Largest Value Gold Coints Suppose V1 and V2 With V1 1.\" \/>\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\/remaining-gold-coin\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Remaining Gold Coin | Greedy Algo Interview Coding | Prepbytes\" \/>\n<meta property=\"og:description\" content=\"You Have a Bag Full of Gold Coins. Each Coin Has a Positive Integer Inscribed on It. in Each Turn You Choose Two Largest Value Gold Coints Suppose V1 and V2 With V1 1.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/\" \/>\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-11T04:51:11+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-05-16T10:40:15+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645181869567-Article_470.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\/remaining-gold-coin\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/\"},\"author\":{\"name\":\"Prepbytes\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\"},\"headline\":\"REMAINING GOLD COIN\",\"datePublished\":\"2020-06-11T04:51:11+00:00\",\"dateModified\":\"2022-05-16T10:40:15+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/\"},\"wordCount\":226,\"commentCount\":0,\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645181869567-Article_470.png\",\"keywords\":[\"greedy algorithm\",\"interview\"],\"articleSection\":[\"Greedy Algo Interview Coding\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/\",\"url\":\"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/\",\"name\":\"Remaining Gold Coin | Greedy Algo Interview Coding | Prepbytes\",\"isPartOf\":{\"@id\":\"http:\/\/43.205.93.38\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645181869567-Article_470.png\",\"datePublished\":\"2020-06-11T04:51:11+00:00\",\"dateModified\":\"2022-05-16T10:40:15+00:00\",\"description\":\"You Have a Bag Full of Gold Coins. Each Coin Has a Positive Integer Inscribed on It. in Each Turn You Choose Two Largest Value Gold Coints Suppose V1 and V2 With V1 1.\",\"breadcrumb\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/#primaryimage\",\"url\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645181869567-Article_470.png\",\"contentUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645181869567-Article_470.png\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/#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\":\"REMAINING GOLD COIN\"}]},{\"@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":"Remaining Gold Coin | Greedy Algo Interview Coding | Prepbytes","description":"You Have a Bag Full of Gold Coins. Each Coin Has a Positive Integer Inscribed on It. in Each Turn You Choose Two Largest Value Gold Coints Suppose V1 and V2 With V1 1.","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\/remaining-gold-coin\/","og_locale":"en_US","og_type":"article","og_title":"Remaining Gold Coin | Greedy Algo Interview Coding | Prepbytes","og_description":"You Have a Bag Full of Gold Coins. Each Coin Has a Positive Integer Inscribed on It. in Each Turn You Choose Two Largest Value Gold Coints Suppose V1 and V2 With V1 1.","og_url":"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/","og_site_name":"PrepBytes Blog","article_publisher":"https:\/\/www.facebook.com\/prepbytes0211\/","article_published_time":"2020-06-11T04:51:11+00:00","article_modified_time":"2022-05-16T10:40:15+00:00","og_image":[{"url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645181869567-Article_470.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\/remaining-gold-coin\/#article","isPartOf":{"@id":"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/"},"author":{"name":"Prepbytes","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e"},"headline":"REMAINING GOLD COIN","datePublished":"2020-06-11T04:51:11+00:00","dateModified":"2022-05-16T10:40:15+00:00","mainEntityOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/"},"wordCount":226,"commentCount":0,"publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645181869567-Article_470.png","keywords":["greedy algorithm","interview"],"articleSection":["Greedy Algo Interview Coding"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/","url":"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/","name":"Remaining Gold Coin | Greedy Algo Interview Coding | Prepbytes","isPartOf":{"@id":"http:\/\/43.205.93.38\/#website"},"primaryImageOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/#primaryimage"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645181869567-Article_470.png","datePublished":"2020-06-11T04:51:11+00:00","dateModified":"2022-05-16T10:40:15+00:00","description":"You Have a Bag Full of Gold Coins. Each Coin Has a Positive Integer Inscribed on It. in Each Turn You Choose Two Largest Value Gold Coints Suppose V1 and V2 With V1 1.","breadcrumb":{"@id":"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/#primaryimage","url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645181869567-Article_470.png","contentUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645181869567-Article_470.png"},{"@type":"BreadcrumbList","@id":"https:\/\/prepbytes.com\/blog\/remaining-gold-coin\/#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":"REMAINING GOLD COIN"}]},{"@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\/1464","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=1464"}],"version-history":[{"count":9,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/1464\/revisions"}],"predecessor-version":[{"id":8386,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/1464\/revisions\/8386"}],"wp:attachment":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/media?parent=1464"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/categories?post=1464"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/tags?post=1464"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}