Mark lives in a tiny country populated by people who tend to over-think things. One day, the king of the country decides to redesign the country's currency to make giving change more efficient. The king wants to minimize the expected number of coins it takes to exactly pay any amount up to (but not including) the amount of the smallest paper bill.

Suppose that the smallest unit of currency is the Coin. The smallest paper bill in the kingdom is worth $n$ Coins. The king decides that there should not be more than $m$ different coin denominations in circulation. The problem, then, is to find a $m$-set $\{d_1, d_2, ..., d_m\}$ of integers from $\{1, 2, ..., n - 1\}$ which minimizes $\frac{1}{n-1}\sum_{i = 1}^{n-1}{c_1(i) + c_2(i) + ... + c_m(i)}$ subject to $c_1(i)d_1 + c_2(i)d_2 + ... c_m(i)d_m = i$.

For instance, take the standard USD and its coin denominations of $\{1, 5, 10, 25, 50\}$. Here, the smallest paper bill is worth 100 of the smallest coin. It takes 4 coins to make 46 cents using this currency; we have $c_1(46) = 1, c_2(46) = 0, c_3(46) = 2, c_4(46) = 1, c_5(46) = 0$. However, if we had coin denominations of $\{1, 15, 30\}$, it would take only 3 coins: $c_1(46) = 1, c_2(46) = 1, c_3(46) = 1$. Which of these denomination sets minimizes the average number of coins to make any sum up to and including 99 cents?

More generally, given $n$ and $m$, how might one algorithmically determine the optimal set? Clearly, one might enumerate all viable $m$-subsets and compute the average number of coins it takes to make sums from 1 to $n - 1$, keeping track of the optimal one along the way. Since there are around $C(n - 1, m)$ $m$-subsets (not all of which are viable, but still), this would not be terribly efficient. Can you do better than that?

  • $\begingroup$ If m < n - 1, then isn't the solution always going to have exactly m denominations? If I have a solution with k coins for (k < m < n - 1) I can always reduce one coin count for a count > 0 to 1 by adding a denomination just for it, thus reducing the average. If that is true, then does that reduce the naive runtime? $\endgroup$ Jul 13, 2012 at 18:22
  • $\begingroup$ @MikeSamuel Sure. However, if there are two equally good solutions, one with $m$ denominations and one with $k < m$ denominations, that might be something the king is interested in knowing. Making more kinds of coins costs money, after all. $\endgroup$
    – Patrick87
    Jul 13, 2012 at 18:24
  • $\begingroup$ I don't think there can be two equally good solutions as defined solely by the summation above when m < n-1. If there is a coin worth k where 1 <= k < n, then that element of the summation is 1, and if there is not a coin worth k, then that element of the summation is > 1. $\endgroup$ Jul 13, 2012 at 18:28
  • $\begingroup$ @MikeSamuel I think that's probably true, but then again, I'd sort of like to see that as part of an answer, possibly with some motivation. It actually gets a little complicated, since the sets can be (mostly) non-overlapping. $\endgroup$
    – Patrick87
    Jul 13, 2012 at 18:32
  • $\begingroup$ Here's another fact that narrows the solution space: a coin worth 1 has to appear in all solutions. $\endgroup$ Jul 13, 2012 at 18:34

4 Answers 4


This is related to the well-known change-making problem. So well-studied, in fact, that this question has been investigated for $m \leq 7$ [1] using brute force. As of 2003, the hardness of finding optimal denominations appears to be an open problem.

If you check the articles citing Shallit, it seems as if denominations enabling greedy change-making strategies were of particular interest. It is clear that such denominations have advantages in practice.

  1. What This Country Needs is an 18c Piece by Jeffrey Shallit (2003)

I guessed (wrongly, but bear with me) that the series $\{b^i |\ b = \lceil n^{1/m} \rceil, 0 \leq i < m\}$ of coins would be the optimal, as the coins would be exponentially spaced, thus reducing the remaining value as much as possible per added coin. For your example, this would be $\{1,3,9,27,81\}$.

This is a notch better ($390/99$) than the USD denominations ($420/99$), but that doesn't have to mean anything.

I wrote a hackish Haskell script to get some numbers by brute force, as I'm not sure right now how to approach this analytically.
It turns out, the exponential distribution is not always the best: there are sometimes slightly better ones, for example, for $(m,n) = (4,30)$ we get $75/29$ for $\{20,8,3,1\}$ but $87/29$ for $\{27,9,3,1\}$. My sluggish machine can't get to $(5,100)$, so we have to use smaller numbers, here.

However, I noticed that the error seems to be quite small. Most of the time, the division of the sums yields something starting with an 1.0..., so I ran some more tests.

From a test set with $3 \leq m \leq 5$ and $6 \leq n \leq 40$, we get an average error of our exponential growing compared to the best solution of $1.12$ with a standard deviation of $0.085$.

You might argue that the test parameters are rather small, but as you point out, it's just a lot to brute force if you set $n = 100$ (there's most probably a better solution, but this was an excellent excuse to slack off and do some Haskell).

Here is my test suite, if you want to try it out:

getopt :: [Integer] -> Integer -> [Integer]
getopt _ 0 = []
getopt coins target = choice:(getopt viable $ target - choice)
                            viable = filter ((>=) target) coins
                            choice = maximum $ viable

getsum :: [Integer] -> Integer -> Int
getsum coins n = sum $ map length $ map (getopt coins) [1..(n-1)]

buildall :: Integer -> Integer -> [[Integer]]
buildall 1 _ = [[1]]
buildall m n = foldl1 (++) $ map (\am -> map (\x -> x:am) [((head am)+1) .. (n-1)]) $ buildall (m-1) n

buildguess :: Integer -> Integer -> [Integer]
buildguess m n = reverse $ map ((^) $ ceiling $ (fromInteger n)**(1.0/(fromInteger m))) [0..(m-1)]

findopt :: Integer -> Integer -> ([Integer],Int)
findopt m n = foldl1 (\(l@(_,lhs)) -> (\(r@(_,rhs)) -> (if (lhs < rhs) then l else r)))
            $ map (\arr -> (arr,getsum arr n)) $ buildall m n

intcast :: (Integral a,Num b) => a -> b
intcast = fromInteger.toInteger

esterror :: Integer -> Integer -> Double
esterror m n = (intcast $ getsum (buildguess m n) n) / (intcast best)
                 where (_,best) = findopt m n

I ran the test with

map (uncurry esterror) [(m,n) | m <- [3..5], n <- [6..40] ]

I found out that for m=2 the set should be {1, floor(√n)+1} or {1, ceil(√n)} unless n is a perfect square times the unit the two numbers are equal, if n is a perfect square,both √n and √n+1 work the best

  • $\begingroup$ As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Sep 13, 2023 at 15:32

I think that the optimal solution is when a denomination is used it should be used at most (m√)n times and also using as close denominations as the value as possible. I tried using {1,3,7,16,40} for n= 100 (or 99) as I tried to generalise the m=2 solution, however 28 is better made as 7+7+7+7 rather than 16+7+3+1+1 and similarly 68 as 40+4×7 rather than 40+16+7+1+1 so it skips using 16 which is closer to 28 than 7 is. Also 21= 7+7+7=16+3+1+1 , 37= 16+7+7+7=16+16+3+1+1, 61= 40+7+7+7=40+16+3+1+1, 77=40+16+7+7+7=40+16+16+3+1+1 Yes I found many. What is interesting about this set is that you can replace 3+3+1 with 7, 7+7+1+1 with 16, 16+16+7+1 with 40, and weirdly 16+3+1+1 with 7+7+7

  • $\begingroup$ As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Sep 13, 2023 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.