Make Exact Change Using the Fewest Notes
Implement fewestNotes
A cash register holds unlimited notes of several denominations. The denominations are in increasing order, the smallest is 1, and every denomination is a whole multiple of the one before it (for example 1, 4, 12, 60). Given an amount, find the fewest notes that add up to exactly that amount.
A dynamic-programming table that works out the answer for every amount up to the target is correct for any denominations, but the special multiple-of-the-previous structure allows a much simpler greedy method: repeatedly take as many of the largest note as fit.
Example 1:
Input: notes = [1,4,12,60], amount = 175
Output: 10
Example 2:
Input: notes = [1,3,9,27], amount = 26
Output: 6
Example 3:
Input: notes = [1,5,10,50,100], amount = 0
Output: 0
+ 9 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ notes.length ≤ 6; notes is strictly increasing, notes[0] = 1, and every note is a whole multiple of the previous one (for example 1, 4, 12, 60) - ●
1 ≤ notes[i] ≤ 500 - ●
0 ≤ amount ≤ 3000 - ●
Any number of each note is available; return the fewest notes that add up to exactly amount (0 if amount is 0)
notes =
amount =