Number of ways to change coins in constant time?

Question

Let's say I have three types of coins -- a penny (0.01), a nickel (0.05), and a dime (0.10) and I want to find the number of ways to make change of a certain amount. For example to change 27 cents:

change(amount=27, coins=[1,5,10])

One of the more common ways to approach this problem is recursively/dynamically: to find the number of ways to make that change without a particular coin, and then deduct that coin amount and find the ways to do it with that coin.

But, I'm wondering if there is a way to do it using a cached value and mod operator. For example:

1. 10 cents can be changed 4 ways:

   • 10 pennies
   • 1 dime
   • 2 nickels
   • 1 nickel, 5 pennies

2. 5 cents can be changed 2 ways:

   • 1 nickel
   • 5 pennies

3. 1-4 cents can be changed 1 way:

   • 1-4 pennies

For example, this is wrong, but my idea was along the lines of:

def change(amount, coins=[1,5,10]):
    cache = {10: 4, 5: 2, 1: 1}
    for coin in sorted(coins, reverse=True):
        # yes this will give zerodivision
        # and a penny shouldn't be multiplied
        # but this is just to demonstrate the basic idea
        ways = (amount % coin) * cache[coin]
        amount = amount % ways
    return ways

If so, how would that algorithm work? Any language (or pseudo-language) is fine.

Answer 1

Precomputing the number of change possibilities for 10 cents and 5 cents cannot be applied to bigger values in a straight forward way, but for special cases like the given example of pennies, nickels and dimes a formula for the number of change possibilities can be derived when looking into more detail how the different ways of change for 5 and 10 cents can be combined.

Lets first look at multiples of 10. Having e.g. n=20 cents, the first 10 cents can be changed in 4 ways, so can the second group of 10 cents. That would make 4x4 = 16 ways of change. But not all combinations are different: a dime for the first 10 cents and 10 pennies for the other 10 cents is the same as having 10 pennies for the first 10 cents and a dime for the second 10 cents. So we have to count the possibilities in an ordered way: that would give (n/10+3) choose 3 possibilities. But still not all possibilities in this counting are different: choosing a nickel and 5 pennies for the first and the second group of 10 cents gives the same change as choosing two nickels for the first group and 10 cents for the second group. Thinking about this a little more one finds out that the possibility of 1 nickel and 5 pennies should be chosen only once. So we get (n/10+2) choose 2 ways of change without the nickel/pennies split (i.e. the total number of nickels will be even) and ((n-10)/10+2) choose 2 ways of change with one nickel/pennies split (i.e. the total number of nickels will be odd).

For an arbitrary number n of cents let [n/10] denote the value n/10 rounded down, i.e. the maximal number of dimes that can be used in the change. The cents exceeding the largest multiple of 10 in n can only be changed in maximally two ways: either they are all pennies or - if at least 5 cents remain - one nickel and pennies for the rest. To avoid counting the same way of change several times one can forbid to use any more pennies (for the groups of 10 cents) if there is a nickel in the change of the 'excess'-cents, so only dimes and and nickels for the groups of 10 cents, giving [n/10]+1 ways.

Alltogether one arrives at the following formula for N, the total number of ways for changing n cents:

N1 = ([n/10]+2) choose 2  +  ([n/10]+1) choose 2  =  ([n/10]+1)^2

       [n/10]+1,  if n mod 10 >= 5
N2 = {
       0,         otherwise

N = N1 + N2

Or as Python code:

def change_1_5_10_count(n):
  n_10 = n // 10
  N1 = (n_10+1)**2
  N2 = (n_10+1) if n % 10 >= 5 else 0
  return N1 + N2

btw, the computation can be further simplified: N = [([n/5]+2)^2/4], or in Python notation: (n // 5 + 2)**2 // 4.