algorithmoptimizationcombinationscoin-change# Number of ways to change coins in constant time?

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:

10 cents can be changed 4 ways:

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

5 cents can be changed 2 ways:

- 1 nickel
- 5 pennies

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.

Solution

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`

.

- How to generate uniformly distributed subintervals of an interval?
- Generating random number in a non-power-of-2 range from random bits
- Algorithm - Search and Replace a string
- Looking for a branchless algorithm for converting a specific set of 4-bit integers
- Different results for XIRR between Excel and ExcelFinancialFunctions 3.2.0
- Find four,whose sum equals to target
- A* algorithm can't find the goal in Python
- Efficiently getting all divisors of a given number
- Are there any existed API to split IEnumerable<T> to many Vector<T> in CSharp？
- Generating all divisors of a number given its prime factorization
- Efficient way to insert a number into a sorted array of numbers?
- BFS Maximize Minimum Distance from a Monster along a path
- Is there effective algorithm that will return all different combination?
- Big O of algorithm that steps over array recursively
- Modification of Dijkstra's algorithm to make it work with negative weights and its time complexity
- Traversing/Moving over an unfolded cube
- Fibonacci Recursion using Golden Ratio(Golden Number)
- Karatsuba implementation in C
- Why is O(n) better than O( nlog(n) )?
- What is Sliding Window Algorithm? Examples?
- How to write a function to navigate through a non-binary tree?
- Evenly distribute QDate values into certain number of slots
- Find max product using divide and conqure in O(n) time
- Cache-friendly sqare matrix transposition logic issue
- Why doesn't Dijkstra's algorithm work for negative weight edges?
- Fast Convertion From Adjacency List to Edge List
- I convert ASCII words into numbers but am stuck trying to decode them. How to convert 1=a, 2=b, 28=ab etc? (psudeocode okay)
- Reversing the word order in a string in place
- Trying to make a 2x2 rubik's cube solving algorithm , how do i find the solution path (DFS)?
- question about missing element in array