Algorithms
Greedy Coin Change
O(n log n) time to sort the coins, then O(n) time to hand them out · O(1) extra space, besides the list of coins used.
The idea, in plain English
A greedy algorithm always grabs the best-looking option available right now, and never looks back. Making change like a cashier is the classic example: hand over the biggest coin that still fits, then the next biggest, and so on. It is fast and often works, but only because everyday coin systems happen to work well with this approach.
How it works
- 1Sort the coin values from largest to smallest.
- 2Take as many of the largest coin as fit into the remaining amount.
- 3Move to the next-smaller coin and repeat, until the remaining amount reaches zero.
When you'd use it
Use it to make change with a standard coin system, like US currency or most real-world money. Use it for any problem where grabbing the best choice right now also gives you the best overall result.
Common beginner mistakes
- Assuming greedy always gives the fewest coins. With an unusual coin system, like [1, 3, 4] for the amount 6, greedy can do worse than the true best answer. Only dynamic programming can guarantee the true best answer.
- Forgetting to sort the coins first, so the biggest coin does not actually get tried first.
Try it — edit and run
Click the code to edit · press ⌘/Ctrl+↵ to run
Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.
Amount: 63
Coins used: 25 25 10 1 1 1
Total coins: 6See it in motion
Make 39 with as few coins as possible — try the largest coins first.
Not sure this is the right topic? See the learning paths → or where this leads →