Fewest Coins for an Amount with Unlimited or Single-Use Coins
Company: Oracle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given coin values `coins` and a target `amount`. Return the fewest coins whose values add up to exactly `amount`, or `-1` if no selection of coins does. The interview asked this in two forms, and `unlimited` selects between them:
- `unlimited = True`: every value in `coins` is a denomination with an unlimited supply, so a value can be used any number of times.
- `unlimited = False`: every element of `coins` is one physical coin that can be used at most once; equal values in the list are separate coins.
The report describes the round only as the classic coin-change problem followed by the variant in which each coin can be used at most once; this version asks for the fewest coins in both forms.
### Function Signature
```python
def fewest_coins(coins: list[int], amount: int, unlimited: bool) -> int:
```
### Rules
- `amount = 0` needs no coins, so the answer is `0` in both forms.
- The answer counts coins, not distinct values: using the value 3 twice counts as two coins.
- Return `-1` when `amount` cannot be formed exactly.
### Constraints
- `1 <= len(coins) <= 100`
- `1 <= coins[i] <= 10^4`
- `0 <= amount <= 10^4`
### Examples
**Example 1**
```text
Input: coins = [1, 3, 4], amount = 6, unlimited = True
Output: 2
```
`3 + 3` uses two coins. Taking the largest coin first gives `4 + 1 + 1`, which uses three.
**Example 2**
```text
Input: coins = [1, 3, 4], amount = 6, unlimited = False
Output: -1
```
With each coin usable once, the reachable totals are 1, 3, 4, 5, 7 and 8, so 6 cannot be formed.
**Example 3**
```text
Input: coins = [2, 5, 2, 2], amount = 6, unlimited = False
Output: 3
```
The three separate 2-coins make 6; the 5-coin is not part of any selection that sums to 6.
Overview: Return the fewest coins that add up exactly to an amount, first when every coin value can be reused without limit and then when each listed coin can be used at most once. An onsite coding problem that tests the difference between unlimited and single-use selection and the handling of amounts that cannot be formed.
Read the full Oracle Software Engineer interview experience this question came from
You are given a list of coin values `coins`, a target `amount`, and a boolean `unlimited`. Return the fewest coins whose values add up to exactly `amount`, or `-1` if no selection of coins does. The interview asked this in two forms, and `unlimited` selects between them:
- `unlimited = True`: every value in `coins` is a denomination with an unlimited supply, so a value can be used any number of times.
- `unlimited = False`: every element of `coins` is one physical coin that can be used at most once; equal values in the list are separate coins.
### Rules
- `amount = 0` needs no coins, so the answer is `0` in both forms.
- The answer counts coins, not distinct values: using the value 3 twice counts as two coins.
- Return `-1` when `amount` cannot be formed exactly.
- The answer is a single integer (at most 10^4), so there is nothing to break ties on. Every input and output value fits in a 32-bit signed integer.
### Constraints
- `1 <= len(coins) <= 100`
- `1 <= coins[i] <= 10^4`
- `0 <= amount <= 10^4`
- `unlimited` is `True` or `False`
### Example 1
```text
Input: coins = [1, 3, 4], amount = 6, unlimited = True
Output: 2
```
`3 + 3` uses two coins. Taking the largest coin first gives `4 + 1 + 1`, which uses three.
### Example 2
```text
Input: coins = [1, 3, 4], amount = 6, unlimited = False
Output: -1
```
With each coin usable once, the reachable totals are 1, 3, 4, 5, 7 and 8, so 6 cannot be formed.
Constraints
- 1 <= len(coins) <= 100
- 1 <= coins[i] <= 10^4
- 0 <= amount <= 10^4
- unlimited is True or False
Examples
Input: ([7], 0, True)
Expected Output: 0
Explanation: amount = 0 needs no coins in the unlimited form.
Input: ([1, 2, 3], 0, False)
Expected Output: 0
Explanation: amount = 0 needs no coins in the at-most-once form.
Hints
- Example 1 shows that always taking the largest coin that fits can use more coins than necessary, so the choice must account for more than the biggest value.
- amount is at most 10^4, so it is feasible to reason about every total from 0 up to amount and how few coins reach each one.
- The two forms differ only in whether a coin is still available after it is used: in the at-most-once form make sure one list element is never counted twice, while equal values at different positions remain separate coins.