naive n coins = f (length coins) n where
f :: Int -> Integer -> Integer
f _ 0 = 1
f 0 _ = 0
f k n = f (k - 1) n + if n < c then 0 else f k (n - c) where
c = coins!!(k - 1)
naive 100 [1, 5, 10, 25]
Compute The Change You Want To See
Today, the circulating coins in the US are the penny, nickel, dime, and quarter, with cent values 1, 5, 10, 25, respectively. How many different ways can we choose coins to sum up to a given amount?
For example, there are 4 ways to make 10 cents: ten pennies; one nickel and five pennies; two nickels; one dime. We’ll later find there are 242 ways to make one dollar, that is, 100 cents.
The above is a well-known problem with well-known relatives. One flavour fixes a finite multiset of coins, rather than provide an endless supply of coins of each type. This is the subset sum problem with inputs restricted to positive integers, whose decisional variant is NP-complete. Another variant asks for the minimum number of coins needed, a special case of the knapsack problem.
Technical interviews frequently test candidates with one of the above problems. In fact, at one place I worked, interviewers were forbidden to ask these problems because it was feared they were too well-known, a concern that may be warranted because several websites reveal how to solve these problems with dynamic programming.
However, there is one subtlety that seems less well-known. For the particular variant of the problem we asked, we can do much better than the solution that is cut-and-pasted all over the web. Exponentially better. See Graham, Knuth, and Patashnik, Concrete Mathematics, Chapter 7.
Exponential Improvement With Exponents
Consider a subset sum problem: how many ways we can pick elements of \(\{6,6,6,9,9,20\}\) so they sum up to 32? This is equivalent to asking for the coefficient of \(x^{32}\) in:
\[ (1+x^6+x^{12}+x^{18})(1+x^9+x^{18})(1+x^{20}) \]
The dynamic programming algorithm for the subset sum problem jumps out. Coefficients of a polynomial naturally correspond to numbers in an array, and multiplying by the next polynomial corresponds to updating the array via dynamic programming.
In our original problem, we may use as many copies of a coin as we want, so we wind up with formal power series instead of polynomials. For a given \(n\), we seek the coefficient of \(x^n\) in:
\[ f = (1 + x + x^2 + …)(1 + x^5 + x^{10} + …) (1 + x^{10} + x^{20} + …)(1 + x^{25} + x^{50} + …) \]
We can recursively find the coefficient of \(x^n\) by taking advantage of the identity:
\[ 1 + z + z^2 + … = 1 + z(1 + z + z^2 + …) \]
where we substitute various powers of \(x\) for \(z\).
Memoization leads to the infamous dynamic programming solution, which is
typically enough to pass the interview. (Haskell’s
Data.MemoTrie
lets us do this by replacing all occurrences of f on the right-hand side with
memo2 f.)
It turns out we’re better off with a different identity:
\[ 1 + z + z^2 + … = \frac{1}{1-z} \]
Differentiating both sides \(m\) times yields the more general:
\[ 1 + {m + 1 \choose m} z + {m + 2 \choose m} z^2 + … = \frac{1}{(1-z)^{m+1}} \]
We start by rewriting \(f\) as:
\[ f = \frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{25})} \]
The authors of Concrete Mathematics then cleverly observe that we can focus on multiples of 5 cents; any remainder must with made up with pennies. However, we want our code to be simple, so forget being clever! We’ll brutally bash our way through.
The lowest common multiple of the exponents is 50, hence every factor in the denominator is a factor of \(1 - x^{50}\). Thus:
\[ f = \frac{(1+x+...+x^{49})(1+x^5+...+x^{45})(1+x^{10}+...+x^{40})(1+x^{25})} {(1-x^{50})^4} \]
We expand the numerator, or rather, we get the computer to do it. The result is a degree-159 polynomial:
\[a_0 + a_1 x + … + a_{159} x^{159} \]
We represent this polynomial by a list of integers [\(a_0, …, a_{159}\)].
p .+. q = zipWith (+) (pad p) (pad q) where pad = take (length p `max` length q) . (++ repeat 0) p .*. [] = [] [] .*. q = [] (a:as) .*. q = map (a *) q .+. (0:(as .*. q)) expand cs m = foldr1 (.*.) $ cofactor <$> cs where cofactor c = 1:concat (replicate (div m c - 1) $ replicate (c - 1) 0 ++ [1]) expand [1, 5, 10, 25] 50
As for the denominator, substituting \(z = x^{50}, m = 3\) into the above identity yields:
\[ \frac{1}{(1-x^{50})^4} = 1 + {4 \choose 3} x^{50} + {5 \choose 3} x^{100} + ... \]
Altogether, we can compute the coefficient of \(x^n\) in \(f\) by writing \(n = 50 q + r\) where \(0 \le r < 50\), then computing:
\[ {q + 3 \choose 3} a_r + {q + 2 \choose 3} a_{r + 50} + {q + 1 \choose 3} a_{r + 100} + ... \]
The following code automates all this. There are some annoying integer type
conversions: the desired total \(n\) is an Integer, but each coin
denomination is an Int. This is because the coin values must be fairly small,
as our algorithm is pseudo-polynomial in terms of the coin values, yet is
polynomial in \(\log n\), the space it takes to represent \(n\), and we wish to
show off how easily we can handle large \(n\).
choose :: Integer -> Integer -> Integer
choose n k
| n < k = 0
| k == 0 = 1
| otherwise = n * choose (n - 1) (k - 1) `div` k
count :: Integer -> [Int] -> Integer
count n cs = sum [choose (m + q - i) m * fromIntegral (fx!!k)
| (k, i) <- zip [r, r+common..length fx - 1] [0..]] where
m = fromIntegral $ length cs - 1
(q, rInteger) = divMod n $ fromIntegral common
r = fromInteger rInteger :: Int
common = foldr1 lcm cs
fx = expand cs common
count 100 [1,5,10,25]
Concrete Mathematics walks through an example with the same coins plus a half-dollar coin, where the goal is to make one million dollars, that is, \(10^8\) cents:
count 100000000 [1,5,10,25,50]
Let’s now answer the trillion-dollar question:
count 100000000000000 [1,5,10,25,50]
Our algorithm is polynomial in \(\log n\) hence is unfazed by six extra zeroes. In contrast, the popular dynamic programming solution would need one million times more time and space to arrive at the above answer.
Chickening Out
I attended an Australian mathematics training camp in 1994. In those days, McDonald’s sold Chicken McNuggets in boxes of 6, 9, or 20. Some of us were given an exercise which asked for the greatest number of McNuggets that cannot be split into the boxes of 6, 9, or 20.
Armed with the answer, we headed to the nearby Macca’s, intending to prank them by asking for exactly 43 Chicken McNuggets. Stereotypes of maths nerds may be uncomfortably close to the truth, as it took a while for one of us (I won’t name names!) to muster the courage to order, and even then, he only ordered 25, afraid that 43 would sound too oddly specific. The cashier immediately realized that 25 was impossible and simply suggested we get 26 instead. Worst. Prank. Ever.
This variant, sometimes called the Frobenius problem, is NP-hard. There exists an algorithm that is polynomial in the values of the denominations but is pseudo-polynomial in the number of denominations. The algorithm is perhaps too abstruse for a short article, let alone a typical coding interview. Luckily, the McNuggets problem is tiny enough that we can bluntly hammer the problem with our code to show 43 is the answer:
(`count` [6, 9, 20]) <$> [43..43+6]
There are zero ways of making 43, while there is at least one way to make each of the next 6 integers. Since one of the box sizes is 6, we can make all larger numbers.
By the way, I sill remember a time when Australian coins had denominations 1, 2, 5, 10, 20, and 50. They’re fun to play with because each features an Australian animal, except for the 50-cent coin, which features two.
How many ways are there to make a million Aussie dollars?
count 100000000 [1,2,5,10,20,50]
Inflation took away the feathertail glider and frill-necked lizard, and gave us the one- and two-dollar coins:
count 100000000 [5,10,20,50,100,200]
It is only after writing this article that I discovered my primary school teacher misled me years ago. She claimed the sugar glider (Pretaurus breviceps) appeared on the one-cent coin, and even made us write about it. According to Wikipedia, it’s actually the feathertail glider (Acrobates pygmaeus). Searching for "sugar glider 1c" returns some results suggesting that others were fed the same falsehoods.
Hoard Coins By Being Greedy
In practice, when making change, people use a greedy algorithm: they repeatedly find the largest denomination less than or equal to the remaining balance and hand it over. For example, if required to pay 32c in the US, we’d give one quarter, then one nickel, then two pennies. In Australia, we’d start with a 20c coin, then a 10c coin, then a 2c coin (back when they existed).
This turns out to make the correct change with the fewest the number of coins in both currencies. However, this strategy fails in general. For example, if the coins in circulation have values of 4, 3, and 1, then the greedy algorithm leads to 6 = 4 + 1 + 1, which is not the fewest number of coins since 6 = 3 + 3.
For a given set of denominations, it is unknown how to quickly tell if the greedy algorithm always returns the solution using the fewest number of coins. Tedious bespoke proofs are all we have. See Section 7.3 of Bird and Gibbons, Algorithm Design with Haskell.