Coding questions · Pinterest
Find the Minimum Number of Coins for an Amount
Find the minimum number of unlimited-denomination coins needed to form an exact target amount. This portable version of the standard referenced problem defines impossible and zero amounts, duplicate denominations, numeric bounds, and two examples for later cross-language console verification.
Implement coin_change(coins, amount). The array coins contains positive integer denominations, and you may use an unlimited number of coins of each denomination. Return the minimum number of coins whose values sum exactly to amount. Return -1 if the amount cannot be formed, and return 0 when amount is zero.
The source identifies the standard problem by its encoded number but gives no interview-specific variant. The numeric bounds below are explicit portable practice assumptions.
Function Contract
coin_change(coins: list[int], amount: int) -> int
Constraints
1 <= len(coins) <= 121 <= coins[i] <= 2^31 - 10 <= amount <= 10000- A denomination may appear more than once in the input without changing the result.
Examples
Example 1
Input: coins = [1, 2, 5], amount = 11
Output: 3
The minimum is three coins: 5 + 5 + 1 = 11.
Example 2
Input: coins = [2], amount = 3
Output: -1
No number of 2-value coins sums to 3.
Find the Minimum Number of Coins for an Amount
Hints
- Build answers for every smaller amount from zero upward.
- Scanning upward for one denomination permits using it more than once.
Approach
Let dp[value] be the fewest coins needed to form value, initialized to an unreachable sentinel except dp[0] = 0. For each denomination no larger than amount, scan values upward so the same coin remains available again, and relax dp[value] from dp[value - coin] + 1. The final state is the minimum over every unlimited combination; duplicates only repeat an already valid relaxation.
- Time complexity: O(n * amount) for n input denominations.
- Space complexity: O(amount) auxiliary space.