FunctionRacerProblemsRace

Fewest Coins for the Fare

EasyDynamic programmingPython, JavaScript, TypeScript, Java, C++

The bus fare is fare cents and the driver only takes exact change. Your pocket holds an unlimited number of coins of each value in coins. Return the smallest number of coins whose values add up to exactly fare. If no combination of the coins can make the fare, return -1. A fare of 0 needs no coins, so return 0 in that case.

Example 1

coins [1,5,12]
fare 15
returns 3

Three 5s make 15; starting with the 12 would need 12 + 1 + 1 + 1, which is four coins.

Example 2

coins [4,6]
fare 7
returns -1

Every total made from 4s and 6s is even, so 7 is impossible.

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 Dynamic programming problems