Make Change

 

Here is a classic from the daily coding challenge a few day's ago

Find the minimum number of coins required to make n cents.

You can use standard American denominations, that is, 1¢, 5¢, 10¢, and 25¢.

For example, given n = 16, return 3 since we can make it with a 10¢, a 5¢, and a 1¢.

Understanding the Problem

We are given an unlimited supply of coins and need to make change such that we return the least number of coins.

US Coins

This is straightforward, if dealing with US coin denominations.

• Pick the highest coin below or equal to the required balance
  • Determine if any more of the same coin can make up the remainder
  • If not, repeat these steps from the beginning with the remainder

Non Standard Coins

This problem however, is really intended to get us to think about a general solution for any coin denominations.

The common example tossed around is the coin denominations of 9,6,5,1. In order to make change for 11, the algorithm in the previous section would result in 3 coins ( 9 and two 1s ). However, the best answer should have been 2 coins (6 and 5)

Recursion

The one way to approach a general solution is to try all possibilities, and seek out the best. The best in this case is the minimum number of coins.

• Pick all the coins less than or equal to the balance, and for each coin
  • If the coin matches the balance - that is our result
  • Otherwise, we have to solve for the remainder (balance - coin) via recursion. The return value is 1 + the result of the recursive call.
• Finally, for all coins, return the result with least number of coins

DP (Dynamic Programming)

The recursive solution above has an exponential runtime. The standard approach to improve this is -

1. Determine the overlapping subproblems.
2. Use a memo to save results of overlapping problems and thus optimize the runtime.
3. Optionally, convert the top down approach to a bottom up approach and avoid the need of a memo

I'm going to skip to step 3.

The bottom up approach involves building a set of solutions for smaller problems and then utilizing those solutions for the bigger problems.

Given the coins 9,6,5,1 we can determine the best way to make change for 11 by starting with 1.

We know that we only have one coin that can be returned in this scenario. However, for 2, we don't have a 2 value coin. We have to utilize the next lowest coin (1) and solve for the remainder which is 1 (2-1). The answer to both these sub problems is already available to us. In this scenario the min number of coins will be 2.

Now to consider the scenario where we have to make change for 7

We have 3 choices

• 6 - in which case we have to solve for 1
• 5 - in which case we have to solve for 2
• 1 - in which case we have to solve for 6

For all the choices, we have solutions from prior subproblems, and can pick the best one.

Similarly, to solve our original problem 11 in the example, we have 4 coin choices to make initially

• 9 - have to solve for 2
• 6 - have to solve for 5
• 5 - have to solve for 6
• 1 - have to solve for 10

The solution is 2, which is the result of us choosing either 6 or 5