Given an unlimited supply of coins of given denominations, find the minimum number of coins required to get a desired change.

For example, consider S = { 1, 3, 5, 7 }

If desired change is 15, the minimum number of coins required is 3

(7 + 7 + 1) or (5 + 5 + 5) or (3 + 5 + 7)

If desired change is 18, the minimum number of coins required is 4

(7 + 7 + 3 + 1) or (5 + 5 + 5 + 3) or (7 + 5 + 5 + 1)

The idea is to use recursion to solve this problem. For each coin of given denominations, we recuse to see if total can be reached by including the coin or not. If choosing the current coin resulted in the solution, we update the minimum number of coins needed. Finally, we return minimum value we get after exhausting all combinations.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <bits/stdc++.h> using namespace std; // Function to find the minimum number of coins required // to get total of N from set S int findMinCoins(int S[], int n, int N) { // if total is 0, no coins are needed if (N == 0) return 0; // return INFINITY if total become negative if (N < 0) return INT_MAX; // initialize minimum number of coins needed to infinity int coins = INT_MAX; // do for each coin for (int i = 0; i < n; i++) { // recuse to see if total can be reached by including // current coin S[i] int res = findMinCoins(S, n, N - S[i]); // update minimum number of coins needed if choosing current // coin resulted in solution if (res != INT_MAX) coins = min(coins, res + 1); } // return minimum number of coins needed return coins; } // main function int main() { // n coins of given denominations int S[] = { 1, 2, 3, 4 }; int n = sizeof(S) / sizeof(S[0]); // Total Change required int N = 15; cout << "Minimum number of coins required to get desired change is " << findMinCoins(S, n, N); return 0; } |

**Output: **

Minimum number of coins required to get desired change is 4

The time complexity of above solution is exponential as each recursive call is making n recursive calls.

The problem has an **optimal substructure** as the problem can be broken down into smaller subproblems which can further be broken down into yet smaller subproblems, and so on. The problem also clearly exhibits **overlapping subproblems** so we will end up solving the same subproblem over and over again. The repeated sub-problems can be seen by drawing recursion tree for higher values of n. We know that problems having optimal substructure and overlapping subproblems can be solved by dynamic programming, in which subproblem solutions are saved rather than computed again and again.

In method is illustrated below, we uses bottom-up approach i.e., we solve smaller sub-problems first, then solve larger sub-problems from them. It computes T[i], for each 1 <= i <= N, which stores minimum number of coins needed to get total of i. It make use of smaller values of i already computed and has the same asymptotic run-time as *Memo*ization but no recursion overhead.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include <bits/stdc++.h> using namespace std; // Function to find the minimum number of coins required // to get total of N from set S int findMinCoins(int S[], int n, int N) { // T[i] stores minimum number of coins needed to get total of i int T[N + 1]; T[0] = 0; // 0 coins are needed to get total of i for (int i = 1; i <= N; i++) { // initialize minimum number of coins needed to infinity T[i] = INT_MAX; int res = INT_MAX; // do for each coin for (int c = 0; c < n; c++) { // check if index doesn't become negative by including // current coin c if (i - S[c] >= 0) res = T[i - S[c]]; // if total can be reached by including current coin c, // update minimum number of coins needed T[i] if (res != INT_MAX) T[i] = min(T[i], res + 1); } } // T[N] stores the minimum number of coins needed to get total of N return T[N]; } // main function int main() { // n coins of given denominations int S[] = { 1, 2, 3, 4 }; int n = sizeof(S) / sizeof(S[0]); // Total Change required int N = 15; cout << "Minimum number of coins required to get desired change is " << findMinCoins(S, n, N); return 0; } |

**Output: **

Minimum number of coins required to get desired change is 4

The time complexity of above solution is O(n^{2}) and auxiliary space used by the program is O(n).

**Exercise:** Find minimum number of coins required to get a desired change from limited supply of coins of given denominations.

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply