Loading
Loading
An old ferry turnstile only accepts metal tokens. Tokens come in a few denominations and you have an unlimited supply of each. The turnstile gives no change, so you must insert exactly the fare.
Given the token denominations and the fare, return the fewest tokens that add up to the fare exactly, or -1 if no combination works.
tokens = [1, 4, 5], fare = 8greedy: 5 + 1 + 1 + 14 tokens — taking the biggest first is not optimalbest[4] = 1, best[5] = 1one token eachbest[8] = min(best[7], best[4], best[3]) + 1last token 1, 4 or 5best[8] = best[4] + 1 = 24 + 42Sign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
Sign in to open hints.
Struggling is where the learning happens. Open this once you have genuinely tried, or once the hints have run out.
O(fare × k) time · O(fare) space
Input. Run your code to watch it work on this input, one line at a time.
Running code is turned off on this deployment. You can still read the problem, write code, use hints and the visualizer.
Tab moves focus out of the editor. Press Ctrl+M to let Tab indent instead.
No results yet
Run your code against the sample tests, or submit to run the full suite.
Two 4-tokens. Taking the 5 first forces 5 + 1 + 1 + 1, four tokens.
Example 2
Only even fares can be paid with 2-tokens.
Example 3
A fare of 0 needs no tokens.