FunctionRacerProblemsRace

Fewest Coins From the Drawer

EasyGreedyPython, JavaScript, TypeScript, Java, C++

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

counts [1,1,3,1,4]
amount 165
returns 4

165 = 100 + 50 + 10 + 5 uses four coins; the drawer has at least one of each of those.

Example 2

counts [0,2,0,0,3]
amount 102
returns 4

There are no 100-cent coins, so 102 = 50 + 50 + 1 + 1 with four coins is the best the drawer can do.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Greedy problems