- Being filled
- Read from
- Answer
Coin change problem
Given a few kinds of coins, how do you pay an exact amount with as few coins as possible, and in how many ways can it be done at all? The greedy answer, biggest coin first, works for real money but fails for some coin sets. A table that builds every amount from smaller ones always gets it right. Tap a coin in the tray to add it to the counter, and tap a coin on the counter to take it back. The meter fills up towards the amount: make it exactly, with as few coins as you can. Fewest coins shows the best answer, and Greedy shows what you get by always taking the biggest coin that fits, which is not always the fewest. Change the coins (in cents) and the amount in the panel. The Table view shows how dynamic programming finds the fewest coins, or counts the number of ways to make the amount: press Play to watch the table fill, or Step and Back to go one step at a time, and drag the step slider to jump anywhere. Each coin can be used as often as you like. With the table selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.
How it works
- Tap coins in the tray to make the amount exactly, and watch the meter fill up in cents.
- Try to use as few coins as possible, then press Fewest coins or Greedy to compare.
- Open the Table view and press Play to watch each cell read the smaller amount it depends on.
Fewest coins
Amount 0 needs no coins. For every larger amount, try each coin that is not bigger than it: what is left after that coin is a smaller amount, already in the table, so one more coin gives a candidate. The smallest candidate goes in the cell, and the coin that gave it is kept in the row underneath. When the table is full, the coins are read back from the target: take its last coin, go to the amount that is left, and repeat until 0.
Number of ways
To count combinations rather than orders, the table adds one coin per row. A cell counts the ways to make its amount with the coins up to its row: the ways without the newest coin, which is the cell above, plus the ways that use the newest coin at least once, which is the cell that many columns to the left in the same row. Because the coins are added in a fixed order, 1 + 2 and 2 + 1 are the same way and are counted once.
Frequently asked questions
Why does the greedy method fail?
Greedy always takes the biggest coin that fits and never reconsiders. With coins 1, 3 and 4 and an amount of 6, it takes 4, then 1 and 1: three coins, where two 3s would do. For coin systems such as the euro or the US dollar, greedy happens to be optimal; such systems are called canonical.
What is the difference between counting ways and counting orders?
Ways treat 1 + 2 and 2 + 1 as the same combination; orders count them separately. The app counts ways, by adding the coins one row at a time. Counting orders instead goes through the amounts and tries every coin for each one.
How fast is the coin change algorithm?
Both tables take the number of coin kinds times the amount steps. That is fast for amounts in the thousands, but an amount can be a huge number, so measured by the number of digits the problem is NP-hard in general.
What if an amount cannot be made?
Its cell stays at ∞, for example amounts 1 and 3 with coins 2 and 5. In the Number of ways mode its count is simply 0.
Is anything sent anywhere?
No. Everything is worked out in your browser, and your last settings stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor