Build a target amount with the fewest coins or notes — a classic problem.
You try
What is the fewest number of US coins (25¢, 10¢, 5¢, 1¢) needed to make 67¢?
The greedy method
- Take the largest coin or note that fits.
- Subtract it; repeat with what's left.
- For US/UK coins this always gives the fewest pieces.
- Curiosity: with some odd coin sets greedy can fail — but not with real currency.
Your turn
Make 95¢ with quarters, dimes, nickels and pennies using the fewest coins.
Cashiers do this in their heads every day — and so do vending machines deciding your change.
Try it
Make 67¢ with quarters, dimes, nickels, pennies
2 quarters (50¢) + 1 dime (60¢) + 1 nickel (65¢) + 2 pennies (67¢) = 6 coins.