Minimum-Coin Combination With Unlimited Coins and a Fixed Tie-Breaking Rule
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You have coins of several denominations and an unlimited number of coins of each denomination. Given a target amount `n`, return the combination of coins that adds up to exactly `n` using as few coins as possible, reported as how many coins of each denomination are used (for example, "three coins of 1" for `n = 3`).
The report recalls five denominations, probably `[1, 5, 10, 15, 20]`. This version takes the denominations as input and fixes the output format and a tie rule so that the answer is unique.
### Function Signature
```python
def min_coin_combination(coins: list[int], n: int) -> list[list[int]]:
```
### Rules
- Return a list of `[denomination, count]` pairs with `count >= 1`, sorted by denomination in ascending order. Denominations that are not used do not appear.
- The total number of coins (the sum of the counts) must be the minimum possible for the amount `n`.
- If several minimum combinations exist, return the one that uses the most coins of the largest denomination; if that is still tied, the most coins of the next largest denomination, and so on. In other words, compare the counts from the largest denomination downward and pick the combination whose first differing count is larger.
- If no combination adds up to `n`, return an empty list.
- `coins` may be given in any order.
### Constraints
- `1 <= len(coins) <= 10`
- `1 <= coins[i] <= 10^5`, and all denominations are distinct
- `1 <= n <= 10^5`
### Examples
**Example 1**
```text
Input: coins = [1, 5, 10, 15, 20], n = 3
Output: [[1, 3]]
```
Only three coins of 1 add up to 3. In the same way, `n = 5` gives `[[5, 1]]`.
**Example 2**
```text
Input: coins = [1, 5, 10, 15, 20], n = 30
Output: [[10, 1], [20, 1]]
```
No single coin is worth 30, so two coins is the minimum, and both `20 + 10` and `15 + 15` use two coins. The tie rule compares counts from the largest denomination: the first uses one coin of 20 and the second none, so `20 + 10` is returned.
**Example 3**
```text
Input: coins = [4, 1, 3], n = 6
Output: [[3, 2]]
```
`3 + 3` uses two coins, and no single coin is worth 6. Starting with the largest coin gives `4 + 1 + 1`, which uses three coins and is therefore not a minimum.
Overview: Given coin denominations with unlimited supply and a target amount, return the combination that reaches the amount with the fewest coins, under a fixed tie-breaking rule. It tests finding an optimal combination when taking the largest coin first can fail, reconstructing the coins used, and handling unreachable amounts.
Read the full Bloomberg Software Engineer interview experience this question came from
You have coins of several distinct denominations, given in `coins` in any order, and an unlimited number of coins of each denomination. Given a target amount `n`, find the combination of coins that adds up to exactly `n` using as few coins as possible, and report how many coins of each denomination it uses.
Implement `min_coin_combination(coins, n)` with these rules:
- Return a list of `[denomination, count]` pairs with `count >= 1`, sorted by denomination in ascending order. Denominations that are not used do not appear.
- The total number of coins (the sum of the counts) must be the minimum possible for the amount `n`.
- If several minimum combinations exist, return the one that uses the most coins of the largest denomination; if that is still tied, the most coins of the next largest denomination, and so on. In other words, compare the counts from the largest denomination downward (an unused denomination counts as 0) and pick the combination whose first differing count is larger.
- If no combination adds up to `n`, return an empty list `[]`.
### Example 1
```text
Input: coins = [1, 5, 10, 15, 20], n = 30
Output: [[10, 1], [20, 1]]
```
No single coin is worth 30, so two coins is the minimum, and both `20 + 10` and `15 + 15` use two coins. Comparing counts from the largest denomination, the first uses one coin of 20 and the second none, so `20 + 10` is returned.
### Example 2
```text
Input: coins = [4, 1, 3], n = 6
Output: [[3, 2]]
```
`3 + 3` uses two coins, and no single coin is worth 6. Starting with the largest coin gives `4 + 1 + 1`, which uses three coins and is therefore not a minimum.
### Constraints
- `1 <= len(coins) <= 10`
- `1 <= coins[i] <= 10^5`, and all denominations are distinct
- `1 <= n <= 10^5`
- Every count in the answer is at most `n`, so all values fit in a signed 32-bit integer (no value exceeds 2^31 - 1).
Constraints
- 1 <= len(coins) <= 10
- 1 <= coins[i] <= 10^5, and all denominations are distinct
- 1 <= n <= 10^5
- coins may be given in any order
- Every count in the answer is at most n, so all values fit in a signed 32-bit integer
Examples
Input: ([1], 1)
Expected Output: [[1, 1]]
Explanation: Minimum valid input: one coin of 1 makes n = 1.
Input: ([7], 21)
Expected Output: [[7, 3]]
Explanation: Single denomination that divides n: three coins of 7.
Hints
- Taking as many coins of the largest denomination as possible is not always minimal: with coins [4, 1, 3] and n = 6 it gives 4 + 1 + 1 (three coins), while 3 + 3 uses two.
- The tie rule only chooses among combinations that already use the minimum total number of coins; it never accepts more coins overall in exchange for more coins of a large denomination.
- Two different combinations always differ in at least one count, so comparing counts from the largest denomination downward always settles a tie.