708. Fewest Coins
A vending machine can pay out change using coins of the denominations listed in coins, and it has an unlimited supply of each denomination. A customer is owed exactly amount units of money.
Return the smallest number of coins that add up to exactly amount. If the amount cannot be formed from the available denominations at all, return -1. When amount is 0 no coins are needed, so return 0. The array may contain the same denomination more than once; that makes no difference.
Aim for time O(amount * k), where k is the number of denominations, and extra space O(amount).
Example 1
- Input:
- coins = [7,4], amount = 15
- Output:
- 3
- Explanation:
Use 7 + 4 + 4 = 15, which takes three coins; no pair of coins reaches 15.
Example 2
- Input:
- coins = [6,10], amount = 9
- Output:
- -1
- Explanation:
Every combination of 6 and 10 is a multiple of 2 and 9 is odd, so the amount is impossible.
Constraints
1 ≤ coins.length ≤ 50
1 ≤ coins[i] ≤ 1000
0 ≤ amount ≤ 105
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 6,000 msC++ 1,500 msJava 3,000 msJavaScript 3,000 msTypeScript 3,000 ms
Expected complexity
- Time
- O(amount * k)
- Space
- O(amount)