Challenge
Find the smallest number of coins whose values sum exactly to amount. Each denomination may be used any number of times. Return -1 if the amount is impossible. Repeated denominations in coins are redundant, not separate supplies.
Input and output contract
0 ≤ amount ≤ 10,000; at most 50 input denominations, each an integer from 1 to 10,000. Empty denominations are allowed. Amount zero always requires zero coins. d is the number of distinct denominations.
All tests follow this contract. You do not need to validate malformed input. Return the requested result from coin_change; printed output is not your answer. Standard-library tools are allowed. Implement your solution in Python 3.12.
Target complexity: O(amount × d + d log(d + 1)) time; O(amount + d) auxiliary space
Return values are checked by type. Use the exact function name. Print output is not your answer. Tests have time and memory limits.
Public examples
Arguments
[[1, 3, 4], 6]
Expected return
2
Arguments
[[2], 3]
Expected return
-1
Arguments
[[], 0]
Expected return
0
Hint
Let best[x] be the minimum coins for total x. Consider the denomination of the last coin.
The worked solution unlocks after completion, or with Premium access.