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

With Python you can leverage the @cache decorator (or @lru_cache) and automatically make a recursive solution into a cached one. For example:

from functools import cache

@cache
def change(amount, coins=(1, 5, 10)):
    if coins==(): return amount==0
    C = coins[-1]
    return sum([change(amount - C*x, coins[:-1]) for x in range(1+(amount//C))])

print(change(27, (1, 5, 10))) # 12
print(change(27, (1, 5))) # 6
print(change(17, (1, 5))) # 4
print(change(7, (1, 5))) # 2

# ch(27, (1, 5, 10)) == ch(27, (1, 5)) + ch(17, (1, 5)) + ch(7, (1, 5))

This will invoke the recursion only for those values of the parameters which the result hasn't been already computed and stored. With @lru_cache, you can even specify the maximum number of elements you allow in the cache.

Answer 2

Almost certainly not for the general case. That's why recursive and bottom-up dynamic programs are used. The modulus operator would provide us with a remainder when dividing the amount by the coin denomination -- meaning we would be using the maximum count of that coin that we can -- but for our solution, we need to count ways of making change when different counts of each coin denomination are used.

Identical intermediate amounts can be reached by using different combinations of coins, and that is what the classic method uses a cache for. O(amount * num_coins):

# Adapted from https://algorithmist.com/wiki/Coin_change#Dynamic_Programming
def coin_change_bottom_up(amount, coins):
  cache = [[None] * len(coins) for _ in range(amount + 1)]

  for m in range(amount+1):
    for i in range(len(coins)):
      # There is one way to return
      # zero change with the ith coin.
      if m == 0:
        cache[m][i] = 1

      # Base case: the first
      # coin (which would be last
      # in a top-down recursion).
      elif i == 0:
        # If this first/last coin
        # divides m, there's one
        # way to make change;
        if m % coins[i] == 0:
          cache[m][i] = 1
        # otherwise, no way to make change.
        else:
          cache[m][i] = 0

      else:
        # Add the number of ways to
        # make change for this amount
        # without this particular coin.
        cache[m][i] = cache[m][i - 1]

        # If this coin's denomintion is less
        # than or equal to the amount we're
        # making change for, add the number
        # of ways we can make change for the
        # amount reduced by the coin's denomination
        # (thus using the coin), again considering
        # this and previously seen coins.
        if coins[i] <= m:
          cache[m][i] += cache[m - coins[i]][i]

  return cache[amount][len(coins)-1]

Answer 3

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.

Answer 4

This will be one of the DP approach for this problem:

def coin_ways(coins, amount):
    dp = [[] for _ in range(amount+1)]
    
    dp[0].append([]) # or table[0] = [[]], if prefer

    for coin in coins:
        for x in range(coin, amount+1):
            dp[x].extend(ans + [coin] for ans in dp[x-coin])
    #print(dp)
    
    return len(dp[amount])


if __name__ == '__main__':
    coins = [1, 5, 10]  #  2, 5, 10, 25]
    print(coin_ways(coins, 27))   # 12