The problem
coins lists the coin values of a country, all different, in any order, and one of them is 1. To pay an amount, the greedy method takes the largest coin that fits, again and again. Return the smallest amount (at least 1) for which the greedy method uses more coins than the fewest possible. If the greedy method is always best, return None.
first_failure([1, 3, 4]) # 6: greedy 4+1+1, best 3+3
first_failure([1, 2, 5, 10, 20, 50, 100, 200, 500]) # None
Lesson 5 gives the fact you need: if greedy ever fails, it fails for some amount below the sum of the two largest coins.
Limits
- Up to 16 coins, the largest up to 100,000. Aim for O(L × k), where L is the sum of the two largest coins and k the number of coins.
Builds on GRDY-5 When greedy fails.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | Coins 1, 3, 4 | Not run | |
| 2 | India's coins and notes | Not run | |
| 3 | Coins 1, 10, 25 | Not run | |
| 4 | Only the 1 | Not run | |
| 5 | Two coins | Not run | |
| 6 | Coins 1, 5, 12 | Not run | |
| 7 | Powers of two | Not run | |
| 8 | Not in order | Not run | |
| 9 | A failure far away | Not run | |
| 10 | A large canonical system | Not run |