{"id":25120,"date":"2017-10-15T14:35:14","date_gmt":"2017-10-15T09:05:14","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25120"},"modified":"2017-10-15T14:35:14","modified_gmt":"2017-10-15T09:05:14","slug":"greedy-algorithm-find-minimum-number-coins","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/greedy-algorithm-find-minimum-number-coins\/","title":{"rendered":"Greedy Algorithm to find Minimum number of Coins"},"content":{"rendered":"

Given a value V, if we want to make change for V Rs, and we have infinite supply of each of the denominations in Indian currency, i.e., we have infinite supply of { 1, 2, 5, 10, 20, 50, 100, 500, 1000} valued coins\/notes, what is the minimum number of coins and\/or notes needed to make the change?<\/span><\/p>\n

Examples:<\/p>\n

Input: V = 70\r\nOutput: 2\r\nWe need a 50 Rs note and a 20 Rs note.\r\n\r\nInput: V = 121\r\nOutput: 3\r\nWe need a 100 Rs note, a 20 Rs note and a \r\n1 Rs coin.<\/pre>\n
\n
Recommended: Please solve it on “PRACTICE<\/u><\/b>” first, before moving on to the solution.<\/h4>\n<\/div>\n[ad type=”banner”]\n
The idea is simple Greedy Algorithm. Start from largest possible denomination and keep adding denominations while remaining value is greater than 0. Below is complete algorithm.<\/p>\n
1) Initialize result as empty.\r\n2) find the largest denomination that is \r\n   smaller than V.\r\n3) Add found denomination to result. Subtract \r\n   value of found denomination from V.\r\n4) If V becomes 0, then print result.  \r\n   Else repeat steps 2 and 3 for new value of V<\/pre>\n
 
 c<\/span> <\/div> 
\/\/ C++ program to find minimum number of denominations#include <bits\/stdc++.h>using namespace std; \/\/ All denominations of Indian Currencyint deno[] = {1, 2, 5, 10, 20, 50, 100, 500, 1000};int n = sizeof(deno)\/sizeof(deno[0]); \/\/ Driver programvoid findMin(int V){    \/\/ Initialize result    vector<int> ans;     \/\/ Traverse through all denomination    for (int i=n-1; i>=0; i--)    {        \/\/ Find denominations        while (V >= deno[i])        {           V -= deno[i];           ans.push_back(deno[i]);        }    }     \/\/ Print result    for (int i = 0; i < ans.size(); i++)           cout << ans[i] << "  ";} \/\/ Driver programint main(){   int n = 93;   cout << "Following is minimal number of change for " << n << " is ";   findMin(n);   return 0;}<\/code><\/pre> <\/div>\n
output:<\/strong><\/h4>\n
Following is minimal number of change for 93 is 50  20  20  2  1<\/pre>\n
Note that above approach may not work for all denominations. For example, it doesn\u2019t work for denominations {9, 6, 5, 1} and V = 11. The above approach would print 9, 1 and 1. But we can use 2 denominations 5 and 6.
\nFor general input, we use below dynamic programming approach.<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Greedy Algorithm to find Minimum number of Coins – Greedy Algorithm – Given a value V, if we want to make change for V Rs. and we have infinite supply of each of the denominations in Indian currency.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,70144],"tags":[71506,71531,71544,71525,71512,71507,71508,71498,70151,71502,71516,71524,71547,71511,71513,71519,71518,71522,71534,71542,70175,71528,71509,71496,71503,71521,71505,71523,70147,71536,71495,71530,71541,71538,71497,71517,70152,70149,71545,71515,71520,71543,71529,71539,71546,71501,71532,71500,71514,71533,71510,71535,71540,71445,71527,71537,71526,71504,71499],"class_list":["post-25120","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-greedy-algorithm","tag-25-cent-coin-value","tag-activity-selection-problem-using-greedy-algorithm-example","tag-application-of-greedy-algorithm","tag-change-coins","tag-change-maker-machine","tag-change-making-problem-java","tag-changemaking","tag-characteristics-of-algorithm","tag-characteristics-of-greedy-algorithm","tag-coin-algorithm","tag-coin-amounts","tag-coin-change","tag-coin-change-problem-using-greedy-algorithm-in-c","tag-coin-changer","tag-coin-changing-algorithm","tag-coin-counting-problem","tag-coin-denominations","tag-coin-making","tag-coin-problems-with-solutions","tag-define-greedy-algorithm","tag-define-greedy-method","tag-denomination-examples","tag-dynamic-coin","tag-dynamic-programming-algorithm","tag-dynamic-programming-explained","tag-dynamic-programming-practice","tag-dynamic-programming-problems-and-solutions","tag-dynamic-programming-table","tag-greedy-algorithm","tag-greedy-algorithm-c","tag-greedy-algorithm-example","tag-greedy-algorithm-examples-pdf","tag-greedy-algorithm-in-c","tag-greedy-algorithm-knapsack-problem-with-example","tag-greedy-algorithm-problems-and-solutions","tag-greedy-algorithm-program-in-c","tag-greedy-algorithm-tutorial","tag-greedy-method","tag-greedy-problems","tag-greedy-program-in-c","tag-how-to-solve-coin-problems","tag-how-to-solve-knapsack-problem-using-greedy-method-example","tag-java-dynamic-programming","tag-knapsack-problem-greedy-algorithm-example","tag-knapsack-problem-greedy-algorithm-explanation","tag-leboncoin","tag-make-a-change","tag-make-algorithm","tag-make-it-change","tag-make-the-change","tag-math-making-change","tag-mcoins","tag-money-changing-problem","tag-pseudo-code-for-greedy-algorithm","tag-quarter-dime-nickel-penny","tag-understanding-dynamic-programming","tag-us-coin-denominations","tag-what-is-dynamic-programming","tag-what-is-the-meaning-of-greedy"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25120","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25120"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25120\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25120"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25120"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25120"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}