Sum using minimum number of coins

Given an infinite supply of coins of different denominations, we want to find if a particular amount can be formed (added-up) using the coins and minimum number of coins that are required to do so.

For example, if the denominations are 1, 2, 5, and 10 and the desired amount is 6, then below are possible solutions by which this amount can be added up:

1. 1 + 5
2. 1 + 1 + 2 + 2
3. 1 + 1 + 1 + 1 + 2
4. 2 + 2 + 2
5. 1 + 1 + 1 + 1 + 1 + 1

Note that the order of coins does not matter here.

Out of all these, first way is the answer since it involves minimum number of coins which will be two. All other ways require three or more coins.

As another example, if the denominations are 5 and 10 and the desired amount is 16, then it is not possible to achieve the desired amount.

Solution

This problem can be solved once we understand that solving puzzle for smaller amounts can lead to the solution of larger amount. The idea is as follows:

Consider that we have say 3 denominations – x, y and z and that for simplicity, we want to achieve sum S which is greater than all denominations. Lets define below:

• A = S – x
• B = S – y
• C = S – z

We can then safely say that –

• If we have added up-to A, we can simply add 1 coin of denomination x to get to S. Similarly, from amounts B and C, we can just add 1 coin of denominations y and z respectively to get to S
• All the ways to get to S have to eventually encounter one of A, B or C on the way. In other words, from any number other than these three, it is not possible to achieve S by adding a single coin.
• If it is not possible to achieve at least one of A, B or C using the specified denominations, then if it is also not possible to achieve sum S.

If we now say that optimal solution to reach sum K means solution with minimum number of coins which add up to K, then we can say below for optimal solution to S:

• An optimal solution for S must also eventually encounter one of A, B, C on the way, like any other solution.
• Any intermediate sum encountered during the solution for S, must itself be optimal way of getting that intermediate sum. This is simply because if say for sum T < S, if way to get T is not optimal, we can always replace that way with optimal way which has fewer coins.
• If optimal solution for S encounters A, the that way to get to A is also optimal (way with fewest coins). Further, optimal solution for S is then simply one plus number of coins required to reach optimal solution for A. (Same is true for B or C). So if we are able to find optimal solutions for A, B and C, then the solution with minimum number of coins will be used to derive optimal solution for S by simply adding 1 to it.

To understand above, lets consider an example where denominations are 1, 2, 5, 10 and the sum to achieve is ₹39. (Here, ₹ is taken as a sample denomination to indicate difference between denomination and number of coins)

As a first claim, we are saying that, any way which gets to 39, must encounter one of 38, 37, 34, or 29.

₹39 = any way to get to ₹38 + 1 coin of ₹1  or
₹39 = any way to get to ₹37 + 1 coin of ₹2  or
₹39 = any way to get to ₹34 + 1 coin of ₹5  or
₹39 = any way to get to ₹29 + 1 coin of ₹10

As a second claim, we are saying that, if we have found optimal way to get to these 4 amounts, then that would lead us to getting optimal way to get to 39, simply by adding one coin to it.

For example, if we have an optimal way to get 38 using say 6 coins, then we can say that optimal way to get 39 via 38 will have 6+1 = 7 coins. Similarly, if we have an optimal way to get to 29 by using say 5 coins, then optimal way to get 39 via 29 will have 5+1 = 6 coins.

Thus what remains is simply (duh !), to find optimal ways to reach 38, 37, 34 and 29 and the optimal way out of these 4 will be the optimal way to get 39. If we already know the answer to these 4, then the answer for 39 become trivial as:

Optimal way for ₹38 = ₹10*3 + ₹5*1 + ₹2*1 + ₹1*1 = 6 coins 
Optimal way for ₹37 = ₹10*3 + ₹5*1 + ₹2*1        = 5 coins 
Optimal way for ₹34 = ₹10*3 + ₹2*2               = 5 coins 
Optimal way for ₹29 = ₹10*2 + ₹5*1 + ₹2*2        = 5 coins 
Hence, optimal way for getting ₹39 will have 1 + 5 = 6 coins. 

Note that, till now we have not exactly solved the problem here. We have simply shifted the bigger problem into solving smaller sub-problems and merely established that solving the sub-problems is guaranteed to solve the actual problem. It is also important to note a pattern here – solving these sub-problems would in-turn result into creating more smaller sub-sub-problems which could be overlapping. For example to get optimal solution for ₹39, we need to solve 4 sub-problems. Two of these are for ₹34 and ₹29. Solving these two sub-problems each would require to solve sub-sub-problem to get ₹24 and so on. However what we have done is, we have created a way to break a bigger problem into smaller ones and we can use this idea to now write mathematical equation as below:

As stated above previously, let us consider that x, y and z are the denominations and S is the desired sum. Also, let A(K) represent the optimal solution (number of coins) to reach to amount K. Then we have:

A(S) = 1 + Min [ A(S-x), A(S-y), A(S-z) ]

The above equation represents what we call as state transition model and tells us how to get to current state from previous “known” states. In this case, if solution to states S-x, S-y, and S-z is known the solution to S can be computed trivially.

Note that, it may seem that the above is just a recurrence relation. One issue with recurrence is that trivial way to solve these sub-problems could involve solving smaller problems over and over again which can result into exponential time complexity. However, since the sub-problems are overlapping, we can use Dynamic programming, which will solve these sub-problems first and stores their answer for future reference (this technique of storing sub-problem outcome is called memoization).

Dynamic Programming is an optimization technique which can be used to specific set of problems which have following two conditions met –

1. The optimization problem can be represented as a recurrence relation
2. There are overlapping sub-problems

We can take an example to see how this works. Consider denominations as 1,2,5 and desired sum S as 9. Then we have:

A(9) = 1 + Min [ A(9-1), A(9-2), A(9-5) ] = 1 + Min [ A(8), A(7), A(4) ] 

So to compute A(9), we need A(8), A(7) and A(4). Taking down further:

A(8) = 1 + Min [ A(8-1), A(8-2), A(8-5) ] = 1 + Min [ A(7), A(6), A(3) ]
A(7) = 1 + Min [ A(7-1), A(7-2), A(7-5) ] = 1 + Min [ A(6), A(5), A(2) ]
A(4) = 1 + Min [ A(4-1), A(4-2) ] = 1 + Min [ A(3), A(2) ] 

So it can be seen that as we go down, computations are repeated. What we do as part of dynamic programming is that, these smaller problems are solved first and their solution is stored. As we solve larger problem, solution to smaller problem is used without recomputing it again thus speeding the process.

In this particular example, we would start from 1 and go up till 9.

Note that we will store all solutions as we compute so that we can reuse them without computing again:

A(1) = 1 since, denomination of 1 is present

A(2) = 1 since, denomination of 2 is present

A(3) = 1 + Min [ A(3-1), A(3-2) ] = 1 + Min [A(2), A(1)] = 1 + Min [1,1] = 2
A(4) = 1 + Min [ A(4-1), A(4-2) ] = 1 + Min [A(3), A(2)] = 1 + Min [2,1] = 2
A(5) = 1 since, denomination of 5 is present

A(6) = 1 + Min [ A(6-1), A(6-2), A(6-5) ] = 1 + Min [A(5), A(4), A(1) ] = 1 + Min [1, 2, 1] = 2
A(7) = 1 + Min [ A(7-1), A(7-2), A(7-5) ] = 1 + Min [A(6), A(5), A(2) ] = 1 + Min [2, 1, 1] = 2
A(8) = 1 + Min [ A(8-1), A(8-2), A(8-5) ] = 1 + Min [A(7), A(6), A(3) ] = 1 + Min [2, 2, 2] = 3
A(9) = 1 + Min [ A(9-1), A(9-2), A(9-5) ] = 1 + Min [A(8), A(7), A(4) ] = 1 + Min [3, 2, 2] = 3

 Hence the solution for desired sum as 9 will be 3 coins (1 of ₹5 + 2 of ₹2)

A key point to note here is that, how these previous states were reached is immaterial to the current state. All that current state cares about is that the solution for previous states is available so that it need not be re-computed.

Another very important point to understand, specifically from implementation perspective is that, it might be possible that we may encounter intermediate sub-problems which are not solvable. For example, if denomination was say 2 and 5, it is not possible to get 1 and 3. The implementation would need to consider this and continue appropriately.

Pseudo-Code

Let S = sum to be achieved
Let D = set of denominations
Let CNT(x) = number of coins which add up to x

1. For all numbers from 1 to S, set CNT(x) = Infinity
2. For all numbers d in D,where d<=S, set CNT(d) = 1
3. For i = 1 to S
4. If (CNT(i) = 1), continue,
5. For all d in D, where d < i
6. CNT(i) = 1 + Min [CNT(i), CNT(i-d)]
7. return CNT(S)

Note that, in step #6 above, the relation derived in previous section is used. A point to remember is, it might be possible that, count for the previous state CNT(i-d) was infinity. This can happen if it is not possible to make sum i-d from the given denominations. (The count would have been calculated in a previous run of loop) This is particularly important from implementation perspective, where a typical practice is to allocate Integer.MAX_VALUE as initial value to the count, since adding 1 to it would overflow the integer.

Solution Code

The method computeMinCoinCount expects the coins array and sum sum and returns the number of coins.
If the sum is not achievable, -1 is returned.
At the start of method, coins array is sorted to handle corner cases. This is not needed from the algorithm perspective itself, but done for some implementation optimization.

 int computeMinCoinCount(int[] coins, int sum) {

	// sort the array - for checking corner cases
	Arrays.sort(coins);

	// if required sum is less than smallest denomination, return -1
	if (sum < coins[0]) {
		return -1;
	}

	// if required sum is an denomination, return 1
	if (Arrays.binarySearch(coins, sum) >= 0) {
		return 1;
	}

	// count[i] indicates minimum number of coins required to achieve sum 'i'
	int[] count = new int[sum + 1];
	count[0] = 0;

	// for all elements from 1 to s, get min coin count
	for (int i = 1; i <= sum; i++) {

		count[i] = Integer.MAX_VALUE;
		
		// if current i is less than smallest denomination, it is not possible to add up to it
		if (i < coins[0]) {
			continue;
		}
		
		// if current i is a denomination, count is simply 1
		if (Arrays.binarySearch(coins, i) >= 0) {
			count[i] = 1;
			continue;
		}

		// for each coin, check if using that coin could result in min count. 
		// Here j is counter for coins
		for (int j = 0; j < coins.length && coins[j] < i; j++) {

			// if a previous state is unreachable, ignore
			if (count[i - coins[j]] == Integer.MAX_VALUE) {
				continue;
			}
			count[i] = Math.min(count[i - coins[j]] + 1, count[i]);
		}
	}

	return count[sum] == Integer.MAX_VALUE ? -1 : count[sum];
}