Fewest coins
The question
A market on Tern gives no change, and its coins come in 1c, 7c, 12c only.
A basket comes to 26c. What is the fewest coins that pay it exactly?
The obvious way to pay is not the fewest
1c7c12c· pay:26c
121211
12cleaves14cto make
1277
- The only coins here are 1c, 7c, 12c, and you must pay exactly 26c.
- First try taking the biggest that fits, again and again: 12 + 12 + 1 + 1 — 4 coins. It works, but is it the fewest?
- Not always: a big coin can leave a remainder the others fit badly, while a smaller one leaves a remainder they fit exactly.
- 12 + 7 + 7 makes 26c in 3 coins, 1 fewer. To be sure 3 is the fewest, work out the best way to pay 1c, 2c, 3c and so on up to 26c — each amount builds on a smaller one.
How it works.
- 01
The only coins here are 1c, 7c, 12c, and you must pay exactly 26c.
- 02
First try taking the biggest that fits, again and again: 12 + 12 + 1 + 1 — 4 coins. It works, but is it the fewest?
- 03
Not always: a big coin can leave a remainder the others fit badly, while a smaller one leaves a remainder they fit exactly.
- 04
12 + 7 + 7 makes 26c in 3 coins, 1 fewer. To be sure 3 is the fewest, work out the best way to pay 1c, 2c, 3c and so on up to 26c — each amount builds on a smaller one.