Find the Minimum Number of Coins for an Amount
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Find the Minimum Number of Coins for an Amount
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) <= 12`
- `1 <= coins[i] <= 2^31 - 1`
- `0 <= amount <= 10000`
- A denomination may appear more than once in the input without changing the result.
## Examples
### Example 1
```text
Input: coins = [1, 2, 5], amount = 11
Output: 3
```
The minimum is three coins: `5 + 5 + 1 = 11`.
### Example 2
```text
Input: coins = [2], amount = 3
Output: -1
```
No number of 2-value coins sums to 3.
Quick Answer: 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). coins contains positive integer denominations, duplicates are allowed, and each denomination may be used without limit. Return the minimum number of coins whose values sum exactly to amount, -1 when amount cannot be formed, and 0 when amount is zero. The numeric bounds are the source's explicit portable practice assumptions for the named standard problem.
Constraints
- 1 <= coins.length <= 12
- 1 <= coins[i] <= 2^31 - 1
- 0 <= amount <= 10,000
- Every denomination may be used an unlimited number of times.
- Duplicate denominations are allowed and do not change the result.
- Return -1 when amount is unreachable and 0 when amount is zero.
Examples
Input: ([1, 2, 5], 11)
Expected Output: 3
Explanation: The first source example uses two fives and one one.
Input: ([2], 3)
Expected Output: -1
Explanation: The second source example is unreachable.
Hints
- Build answers for every smaller amount from zero upward.
- Scanning upward for one denomination permits using it more than once.