Problem

Given a amount ‘A’ and n coins/denominations   v1<v2<v3<………..<vn . Write a program to find out minimum numbers of coins required to make the change for the amount ‘A’. It is also given the coin system is canonical.

OR

Find the minimum number of coins needed to change the input value (an integer) into coins with denominations 1, 5, and 10.

Examples

Example 1:

1
2
3
4
5

Input: coins = [1, 2, 5, 10, 20, 50, 100, 500, 1000], amount = 5
Output: 1
No of ways to make the change are : { 1,1,1,1,1} , {1,1,1,2}, {2,2,1},{5}

So as we can see minimum number of coins required are 1 ({5})

Solution

For some type of coin system (canonical coin systems — like the one used in the India, US and many other countries) a greedy approach works. The valued coins will be like { 1, 2, 5, 10, 20, 50, 100, 500, 1000}. i.e. In our algorithm we always choose the biggest denomination, subtract the all possible values and going to the next denomination.

Method 1 - Greedy

Pseudocode

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

# Denominations of Indian Currency
deno = [1, 2, 5, 10, 20, 50, 100, 500, 1000]
n = len(deno)
 
def findMin(V)
    ans = []
    i = n-1       
    while (i>=0):
        while (V >= deno[i]):
           V = V - deno[i]
           ans.append(deno[i])
        i -= 1
    for coin in ans:
       print coin
V = 93
findMin(V)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

static void findMin(int[] coins, int amount) {
	// Initialize result  
	List<Integer> ans = new ArrayList<>();

	// Traverse through all denomination  
	for (int i = n - 1; i >= 0; i--) {
		// Find denominations  
		while (amount >= coins[i]) {
			amount -= coins[i];
			ans.add(coins[i]);
		}
	}

	return ans;
}

Variant - Just Calculate the Min Change

This code is very similar to above, just that we dont need a list to keep track of coins:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

static int[] denoms = { 1, 5, 10 };
private static int getChange(int m) {
	//write your code here
	int change = 0;
	int moneyRemaining = m;
	for (int i = denoms.length - 1; i >= 0; i--) {
		int currDenom = denoms[i];
		int currChange = moneyRemaining / currDenom;
		moneyRemaining = moneyRemaining % currDenom;

		change += currChange;
		if (moneyRemaining == 0) {
			break;
		}
	}

	return change;
}