FunctionRacerProblemsRace

Coins to Add for Every Total

HardArraysPython, JavaScript, TypeScript, Java, C++

coins is sorted from small to large. You want to be able to pay every total from 1 to target exactly, using each coin at most once. Return the fewest coins, of any values you choose, that must be added to make that possible.

Example 1

coins [1,3]
target 6
returns 1

With 1 and 3 the total 2 cannot be paid. Adding a 2 covers everything up to 6.

Example 2

coins [1,5,10]
target 20
returns 2

Add 2 and 4: then 1, 2, 4, 5 and 10 pay every total up to 22.

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 Arrays problems