Quick 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.

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

  1. 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.
  2. 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.
  3. Two different combinations always differ in at least one count, so comparing counts from the largest denomination downward always settles a tie.

Fewest Coins with a Largest-Denomination-First Tie Rule

mediumBloombergSoftware Engineer

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

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

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).

Examples

Example 1
Input
([1], 1)
Output
[[1, 1]]
Notes
Minimum valid input: one coin of 1 makes n = 1.
Example 2
Input
([7], 21)
Output
[[7, 3]]
Notes
Single denomination that divides n: three coins of 7.

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

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def min_coin_combination(coins: list[int], n: int) -> list[list[int]]:
Sample call
min_coin_combination([1], 1)
Language
Case 1
Input
([1], 1)
Expected
[[1, 1]]
Case 2
Input
([7], 21)
Expected
[[7, 3]]

Browse More Questions

Show the approach

Approach

Sort the denominations ascending as a_1 < a_2 < ... < a_k. Let g_j[x] be the minimum number of coins that make amount x using only a_1..a_j, with g_0[0] = 0 and every other g_0 value impossible (stored as n + 1, which exceeds any real count because every coin is worth at least 1). With an unlimited supply of a_j, g_j[x] = min(g_{j-1}[x], g_j[x - a_j] + 1), so each table is filled left to right in O(n). If g_k[n] is impossible, no combination reaches n and the answer is [].

Otherwise rebuild the answer from the largest denomination down. Keep the remaining amount r (initially n) and the invariant that the counts already fixed plus g_j[r] equal the global minimum g_k[n]. The minimum combinations of a_1..a_j for r are exactly those that use some count c of a_j with g_{j-1}[r - ca_j] + c = g_j[r], completed by a minimum combination of a_1..a_{j-1} for r - ca_j. The tie rule asks for the most coins of the larger denomination first, so take the largest such c (try c = floor(r / a_j) downward; one value always works because g_j[r] is the minimum of that expression over c). This keeps the invariant for j - 1, and after a_1 the remaining amount is 0. Because any two different combinations differ in some count, the result is the single combination the rule selects.

The counts are stored by sorted denomination, so the pairs come out ascending; zero counts are skipped. Edge cases: denominations larger than n never change a table (the inner loop is empty) and get count 0; parity or divisibility gaps (for example only even coins and odd n) leave g_k[n] impossible and return []; a single denomination yields one pair or []. Every count is at most n <= 10^5, so 32-bit integers suffice. The k + 1 tables hold at most 11 * (10^5 + 1) integers.

Time complexity:
O(k log k + n * k), where k = len(coins)
Space complexity:
O(n * k)