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.

Krute

Sounds interesting. Can you elaborate a bit, i dont understand your notation at the end there with the mods and divides – Cherice

@Cherice I annotated it a bit, does that help? – Krute

What you describe sounds like a memoized (or perhaps bottom-up dynamic program) version of the common recursive procedure. Can you write your algorithm in actual code so that it's clearer what you mean? – Tamberg

Yep, you basically have already written the pseudo code for us, why dont you try it out and see what happens, and we can take it from there? – Cherice

Btw I think I can see what you are after, a constant time algorithm that just looks at the amount of ways to change into 10s, then multiply that with the remaining number of ways to change 5s and finally 1s. That wont work, because you need to order the coins by value, which is not a linear operation. Need to think a bit more about it.... but again, post some draft of an algorithm and we take it from there. – Cherice

Yes, there is a DP caches solution. However, the parameter need to specify the coin denomination, not the numbers. I'd post some code if that's helpful. – Zonate

@DanielHao yes that would be fantastic to show the DP caches solution. – Krute

@Cherice I added a pseudo-template and a bounty as well! Let me know if that's helpful. – Krute

Can you be more specific about what's your 'goal' - the thing you need? – Zonate

Btw if you are looking for a formula I would ask it in math.stackexchange – Cherice

I do not think you can do that in constant time. You have a fixed number of denominations, which is okay, but then you can have increasing number of total size of the knapsack, your DP table grows (bottom up memorisation or top down), that will definitely have a growth of time wrt. your knapsack size. Therefore, no constant time. Although, if you have an upper bound of your knapsack size, technically speaking, that becomes constant time. NOTE: check pseudo-polynomial time algorithms. – Misspell

@Misspell thanks, any suggestions for a resource for check pseudo-polynomial time algorithms. ? – Krute

One thing not to miss is a look at the formulae – Undo

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.

Bigg

by [ ... ] at the end you mean |_ ... _|, i.e. floor? – Wismar

@WillNess yes, [...] for floor is the notation used by Gauß; it is still used this way in German speaking countries, see de.wikipedia.org/wiki/… – Bigg

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]

Hagride

Answer 3

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.

Kite

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

Zonate

how does that approach use caching though? – Krute

"cached" may be misleading word, it really mean list all permutations of coins (made up the change). (if you modify last statement to- ``` return dp[amount] ``` - you will know what I mean. – Zonate

OP asks for a solution that is not recursive or dynamic, this is obviously the way to go otherwise. – Cherice