A tollgate charges an exact fare of F units and gives no change. You carry an unlimited supply of coins in each of n distinct denominations. Pay the fare using as few coins as possible. Report the minimum number of coins whose values add up to exactly F, or -1 if the fare cannot be paid exactly with the available denominations.
Line 1: two integers n and F.
Line 2: n space-separated distinct integers, the coin denominations.
A single integer: the minimum number of coins summing to exactly F, or -1 if impossible.
Example 1
Input
3 11 1 2 5
Expected
3
Explanation
5 + 5 + 1 = 11 uses three coins, and no combination of these denominations makes 11 with fewer.
Example 2
Input
2 3 2 4
Expected
-1
Explanation
Only even totals are reachable with denominations 2 and 4, so the odd fare 3 is impossible and the answer is -1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →