Fewest coins or notes to make an amount
Coding problemMediumAsked in: Amazon
You have coins (or notes) of the values given in coins, and as many of each as you want. Return the fewest coins that add up exactly to amount. If no combination makes the amount, return -1. An amount of 0 needs 0 coins.
Taking the largest coin first does not always work: with coins 1, 3 and 4, the amount 6 needs only two coins (3 + 3), but largest-first gives three (4 + 1 + 1).
Examples
Example 1
Input: coins = [1,2,5], amount = 11
Output: 3
5 + 5 + 1.
Example 2
Input: coins = [2], amount = 3
Output: -1
Example 3
Input: coins = [1,3,4], amount = 6
Output: 2
Constraints
- Between 1 and 12 distinct coin values, each between 1 and 10,000
- 0 <= amount <= 10,000
Run checks the 3 examples. Submit also runs the hidden tests: edge cases, large inputs and a time limit.
Run your code to see the results here. Ctrl or Cmd + Enter runs; add Shift to submit.