{"id":3297,"date":"2021-10-31T12:09:18","date_gmt":"2021-10-31T06:39:18","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3297"},"modified":"2022-06-15T11:48:09","modified_gmt":"2022-06-15T06:18:09","slug":"coin-change-problem","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/coin-change-problem\/","title":{"rendered":"Coin Change Problem"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#simple-approach\">Simple Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#efficient-approach-dynamic-programming\">Efficient Approach: Dynamic Programming<\/a><\/li><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><li><a href=\"#practice-question\">Practice Question<\/a><\/li><li><a href=\"#faqs\">FAQs<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3300 pk-lazyload\"  width=\"227\"  height=\"260\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 227px) 100vw, 227px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-10.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-10.png 540w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-10-262x300.png 262w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-10-380x435.png 380w\" ><\/figure><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>We are given an array of coins having different denominations and an integer sum representing the total money, you have to return the fewest coins that you will need to make up that sum if it\u2019s not possible to construct that sum then return -1.<\/p>\n\n\n\n[we have an infinite amount of coins of each type]\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3302 pk-lazyload\"  width=\"522\"  height=\"447\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 522px) 100vw, 522px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-3.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-3.png 698w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-3-300x257.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-3-380x326.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-3-550x471.png 550w\" ><\/figure><\/div>\n\n\n\n<p><strong>Example :&nbsp;<\/strong><\/p>\n\n\n\n<p><strong>Input: <\/strong>[1,2,3,4,5]<br><strong>Sum: <\/strong>16<br><strong>Output: <\/strong>4<br><strong>Explanation:<\/strong> Four coins require to make the desired sum [5,5,5,1]\n\n\n\n<p><strong>Input: <\/strong>[1,2,5,9,8]<br><strong>Sum: <\/strong>17<br><strong>Output: <\/strong>2<br><strong>Explanation:<\/strong> Two coins require to make the desired sum [9,8]\n\n\n\n<p><strong>Input: <\/strong>&nbsp;[2, 4, 6, 8]<br><strong>Sum: <\/strong>15<br><strong>Output: <\/strong>-1<br><strong>Explanation:<\/strong> There is no combination present with sum 15.<\/p>\n\n\n\n<h2 id=\"simple-approach\">Simple Approach<\/h2>\n\n\n\n<p>The naive approach is to check for every combination of coins for the given sum.<\/p>\n\n\n\n<p>In this approach, we can use recursion to solve this as we have to iterate over all the possible combinations of coins that equal the given sum every time update the minimum no of coins needed to create this sum.<\/p>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\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=\"\">int coinChange(vector&lt;int> const &amp;S, int sum)\n{\n    if (sum == 0) {\n        return 0;\n    }\n    if (sum &lt; 0) {\n        return INT_MAX;\n    }\n    int coins = INT_MAX;\n    for (int i: S)\n    {\n        int result = coinChange(S, sum - i);\n        if (result != INT_MAX) {\n            coins = min(coins, result + 1);\n        }\n    }\n    return coins;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\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=\"\">public static int coinChange(int[] S, int sum)\n    {\n        if (sum == 0) {\n            return 0;\n        }\n        if (sum &lt; 0) {\n            return Integer.MAX_VALUE;\n        }\n        int coins = Integer.MAX_VALUE;\n        for (int c: S)\n        {\n            int result = coinChange(S, sum - c);\n\n            if (result != Integer.MAX_VALUE) {\n                coins = Integer.min(coins, result + 1);\n            }\n        }\n        return coins;\n    }<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\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=\"\">def coinChange(S, sum):\n\n    if sum == 0:\n        return 0\n\n    if sum &lt; 0:\n        return sys.maxsize\n\n    coins = sys.maxsize\n\n    for c in S:\n\n        result = coinChange(S, sum - c)\n\n        if result != sys.maxsize:\n            coins = min(coins, result + 1)\n\n    return coins<\/pre>\n\n\n\n<p><strong>Time complexity:<\/strong> Exponential. (every recursive call is making n recursive calls)<br><strong>Space complexity:<\/strong> O(1)<\/p>\n\n\n\n<h2 id=\"efficient-approach-dynamic-programming\">Efficient Approach: Dynamic Programming<\/h2>\n\n\n\n<p>As the problem can be broken down into smaller subproblems as there are many overlapping subproblems in the recursive tree and we will avoid solving them again and again.<\/p>\n\n\n\n<p>We are using a bottom-up approach i.e we solve the small problem first then move to larger subproblems from the smaller ones as we will compute dp[i] 1&lt;=i&lt;=subproblems storing the ans as minimum coins needed to create the sum.<\/p>\n\n\n\n<ul><li><strong>Defining subproblems:<\/strong> CoinChange needed for any x values smaller than n, # subproblems O(n)<br>DP(x)<\/li><li><strong>Make a guess that would take us one step closer to the solution:<\/strong><br>which coin to take<\/li><li><strong>Recurrence or relate the subproblems together:<\/strong><br>DP(x) = min([DP(x-c) for c in coins]) + 1 # time per subproblem O(len(coins))<\/li><li><strong>Think about the topological orders for bottom up implementation:<\/strong><br>We want to know the value with smaller x first, so the for loop starts from 0.<br>The initial state DP(0) = 0, take 0 coin for amount 0<\/li><li><strong>Define the original problem\/think whether the DP can solve the original problem:<\/strong><br>DP(n) Also remember to think of implementation details\/corner cases at this step, for instance, how to deal with x-c&lt;0 in steps 3.<\/li><\/ul>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"858\"  height=\"619\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3301 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 858px) 100vw, 858px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-13.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-13.png 858w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-13-300x216.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-13-768x554.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-13-380x274.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-13-550x397.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-13-800x577.png 800w\" ><\/figure>\n\n\n\n<h2 id=\"c-implementation\">C++ Implementation<\/h2>\n\n\n\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=\"\">int coinChange(vector&lt;int> const &amp;arr, int sum)\n{\n    int dp[sum + 1];\n    for (int i = 1; i &lt;= sum; i++)\n    {\n        dp[i] = INT_MAX;\n        int result = INT_MAX;\n\n        for (int c: arr)\n        {\n            if (i - c >= 0) {\n                result = dp[i - c];\n            }\n\n            if (result != INT_MAX) {\n                dp[i] = min(dp[i], result + 1);\n            }\n        }\n    }\n\n    return dp[sum];\n}<\/pre>\n\n\n\n<h2 id=\"java-implementation\">Java Implementation<\/h2>\n\n\n\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=\"\">public static int coinChange(int[] S, int sum)\n    {\n        int[] dp = new int[sum + 1];\n\n        for (int i = 1; i &lt;= sum; i++)\n        {\n            dp[i] = Integer.MAX_VALUE;\n            int result = Integer.MAX_VALUE;\n\n            for (int c: S)\n            {\n                if (i - c >= 0) {\n                    result = dp[i - c];\n                }\n\n                if (result != Integer.MAX_VALUE) {\n                    dp[i] = Integer.min(dp[i], result + 1);\n                }\n            }\n        }\n\n        return dp[sum];\n    }<\/pre>\n\n\n\n<h2 id=\"python-implementation\">Python Implementation<\/h2>\n\n\n\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=\"\">def coinChange(S, sum):\n\n    dp = [0] * (sum + 1)\n\n    for i in range(1, sum + 1):\n\n        dp[i] = sys.maxsize\n\n        for c in range(len(S)):\n            if i - S[c] >= 0:\n                result = dp[i - S[c]]\n\n                if result != sys.maxsize:\n                    dp[i] = min(dp[i], result + 1)\n\n    return dp[sum]<\/pre>\n\n\n\n<p><strong>Time complexity:<\/strong> O(n*sum)&nbsp; n- no of distinct coins, sum- desired sum.<br><strong>Space complexity:<\/strong> O(sum)<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-question\">Practice Question<\/h2>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/problems\/coin-sum-infinite\/\">Coin Sum Infinite<\/a><br><a href=\"https:\/\/www.interviewbit.com\/courses\/programming\/dynamic-programming\/\" target=\"_blank\" rel=\"noreferrer noopener\">Dynamic Programming<\/a><\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<p><strong>How do you solve a coin change problem?<\/strong><br>We solve the coin change problem using dynamic programming<\/p>\n\n\n\n<p><strong>What is the time complexity of the coin change problem?<\/strong><br>The time complexity of the coin change problem is O(n*sum) n is the no of distinct coins and sum is the target sum we have to create.<\/p>\n\n\n\n<p><strong>Is coin change greedy?<\/strong><br>No, it can\u2019t be solved using the greedy approach.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement We are given an array of coins having different denominations and an integer sum representing the&hellip;\n","protected":false},"author":5,"featured_media":3303,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[518,399],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3297"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3297"}],"version-history":[{"count":3,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3297\/revisions"}],"predecessor-version":[{"id":9808,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3297\/revisions\/9808"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3303"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3297"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3297"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3297"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}