Fewest Coins From the Drawer
A cash drawer holds coins worth 100, 50, 10, 5 and 1 cents. counts[i] is how many coins of the i-th value are in the drawer, in that same order, so counts[0] is the number of 100-cent coins and counts[4] the number of 1-cent coins. Every value here is a multiple of the next smaller one, so taking the largest coin that still fits, as long as the drawer has one, is always best.
Return the fewest coins from the drawer that add up to exactly amount cents, or -1 if the drawer cannot make amount exactly. When amount is 0, return 0.
Example 1
165 = 100 + 50 + 10 + 5 uses four coins; the drawer has at least one of each of those.
Example 2
There are no 100-cent coins, so 102 = 50 + 50 + 1 + 1 with four coins is the best the drawer can do.
Constraints
len(counts) == 50 <= counts[i] <= 200 <= amount <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.