dynamic-programming · Problem 5 of 5
Coin Change
hard
Amazon
Google
Uber
AmazonGoogleUberReturn the fewest coins from coins that sum to amount, or -1 if it cannot be made.
coinChange([1, 2, 5], 11) -> 3Your solution
Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.
Running is free — Submit is what records it. Or press ⌘↩
Tests
4 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| coinChange([1,2,5], 11) | classic | 3 | — |
| coinChange([2], 3) | impossible | -1 | — |
| coinChange([1], 0) | zero amount | 0 | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Complexity
- target time
- O(amount × coins)
- target space
- O(amount)
The greedy-trap case is the point: [1,3,4] for 6 is 3+3, but greedy takes 4 then two 1s. Greedy only works for special coin systems.
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left