Problem Description

You have an integer array coins representing different coin denominations and an integer k. You have an infinite supply of coins of each denomination.

The key constraint is that you cannot combine coins of different denominations - you can only use multiple coins of the same denomination to form amounts.

For example, if coins = [3, 5], you can form:

• Using only coins of value 3: 3, 6, 9, 12, 15, 18, ...
• Using only coins of value 5: 5, 10, 15, 20, 25, ...

The valid amounts you can make are: 3, 5, 6, 9, 10, 12, 15, 18, 20, ...

Your task is to find the k-th smallest amount that can be formed following this rule.

For instance, if coins = [3, 5] and k = 4, the first few smallest amounts are 3, 5, 6, 9, so the answer would be 9.

The problem asks you to return this k-th smallest amount as an integer.

Intuition

The key insight is to recognize that this problem has a monotonic property: if we can form at least k amounts that are less than or equal to some value x, then we can definitely form at least k amounts for any value greater than x. This monotonicity suggests using binary search.

Instead of directly finding the k-th smallest amount, we can reframe the problem: find the smallest value x such that there are exactly k amounts we can form that are less than or equal to x.

For a given value x, how do we count how many valid amounts are ≤ x?

For a single coin of value a, the amounts we can form are a, 2a, 3a, .... The number of these amounts that are ≤ x is ⌊x/a⌋.

With multiple coins, we might think to just sum up ⌊x/coins[i]⌋ for each coin, but this would overcount. For example, with coins [3, 6], the amount 6 can be formed using either 2×3 or 1×6, but we should only count it once.

This is where the inclusion-exclusion principle comes in. Some amounts can be formed by multiple coins - specifically, amounts that are multiples of the LCM (Least Common Multiple) of those coins.

For coins [a, b]:

• Add amounts formed by a: ⌊x/a⌋
• Add amounts formed by b: ⌊x/b⌋
• Subtract amounts formed by both (multiples of lcm(a,b)): ⌊x/lcm(a,b)⌋

This pattern extends to any number of coins using inclusion-exclusion: add counts for single coins, subtract counts for pairs (to remove duplicates), add back counts for triples (since we over-subtracted), and so on.

Since we have at most 15 coins, we can use bit manipulation to enumerate all possible subsets (2^15 possibilities) and apply inclusion-exclusion to get the exact count of valid amounts ≤ x.

Once we can count amounts for any x, binary search finds the smallest x where the count reaches k.

Learn more about Math, Binary Search and Combinatorics patterns.

Solution Approach

The solution uses binary search combined with the inclusion-exclusion principle to find the k-th smallest amount.

Binary Search Setup: We use bisect_left to find the smallest value x where check(x) returns True. The search range is from 0 to 10^11 (a sufficiently large upper bound).

The check Function: This function determines if there are at least k valid amounts less than or equal to mx.

The implementation uses bit manipulation to enumerate all non-empty subsets of coins:

• We iterate from 1 to 2^n - 1 where n = len(coins)
• Each number i represents a subset: if the j-th bit is set, we include coins[j]

Inclusion-Exclusion Implementation: For each subset represented by i:

1. Calculate LCM of the subset:

   v = 1
   for j, x in enumerate(coins):
       if i >> j & 1:  # Check if j-th bit is set
           v = lcm(v, x)
           if v > mx:  # Optimization: stop if LCM exceeds mx
               break

2. Apply inclusion-exclusion rule:

   m = i.bit_count()  # Number of coins in this subset
   if m & 1:  # Odd number of elements
       cnt += mx // v  # Add
   else:  # Even number of elements
       cnt -= mx // v  # Subtract

   • For subsets with odd number of elements: add ⌊mx/LCM⌋
   • For subsets with even number of elements: subtract ⌊mx/LCM⌋

Why this works:

• Single coins (odd size = 1): We add counts like ⌊mx/a⌋, ⌊mx/b⌋
• Pairs of coins (even size = 2): We subtract overlaps like ⌊mx/lcm(a,b)⌋
• Triples (odd size = 3): We add back over-corrections like ⌊mx/lcm(a,b,c)⌋
• And so on...

Final Binary Search: bisect_left(range(10**11), True, key=check) finds the smallest value where check returns True, which is exactly the k-th smallest amount we can form.

The time complexity is O(2^n × log(max_value)) where n is the number of coins (at most 15), making this approach efficient for the given constraints.

Example Walkthrough

Let's walk through finding the 4th smallest amount with coins = [3, 6] and k = 4.

Step 1: Understanding what amounts we can form

• Using coin 3: 3, 6, 9, 12, 15, ...
• Using coin 6: 6, 12, 18, 24, ...
• Combined (sorted): 3, 6, 9, 12, ... (note that 6 appears in both but we count it once)

Step 2: Binary Search Process

We'll search for the smallest value x such that there are at least 4 amounts ≤ x.

Let's trace through some binary search iterations:

Check x = 5:

• Subsets to consider: {3}, {6}, {3,6}
• Subset {3} (size=1, odd): Add ⌊5/3⌋ = 1
• Subset {6} (size=1, odd): Add ⌊5/6⌋ = 0
• Subset {3,6} (size=2, even): Subtract ⌊5/lcm(3,6)⌋ = ⌊5/6⌋ = 0
• Total count = 1 + 0 - 0 = 1
• Since 1 < 4, we need a larger x

Check x = 10:

• Subset {3} (size=1, odd): Add ⌊10/3⌋ = 3 (amounts: 3, 6, 9)
• Subset {6} (size=1, odd): Add ⌊10/6⌋ = 1 (amount: 6)
• Subset {3,6} (size=2, even): Subtract ⌊10/lcm(3,6)⌋ = ⌊10/6⌋ = 1 (overlap: 6)
• Total count = 3 + 1 - 1 = 3
• Since 3 < 4, we need a larger x

Check x = 12:

• Subset {3} (size=1, odd): Add ⌊12/3⌋ = 4 (amounts: 3, 6, 9, 12)
• Subset {6} (size=1, odd): Add ⌊12/6⌋ = 2 (amounts: 6, 12)
• Subset {3,6} (size=2, even): Subtract ⌊12/lcm(3,6)⌋ = ⌊12/6⌋ = 2 (overlaps: 6, 12)
• Total count = 4 + 2 - 2 = 4
• Since 4 ≥ 4, this satisfies our condition!

Check x = 11:

• Subset {3} (size=1, odd): Add ⌊11/3⌋ = 3
• Subset {6} (size=1, odd): Add ⌊11/6⌋ = 1
• Subset {3,6} (size=2, even): Subtract ⌊11/6⌋ = 1
• Total count = 3 + 1 - 1 = 3
• Since 3 < 4, x = 11 is too small

Step 3: Binary Search Conclusion

The binary search finds that x = 12 is the smallest value where we have at least 4 amounts ≤ x.

Therefore, the 4th smallest amount is 12.

We can verify: The amounts in order are 3, 6, 9, 12, and indeed 12 is the 4th one.

Key Insight from the Example: Notice how inclusion-exclusion correctly handled the overlap at 6 and 12:

• Both values were counted once by coin 3 and once by coin 6
• The subtraction of lcm(3,6) = 6 removed these duplicates
• This gave us the exact count of unique amounts

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × 2^n × log(k × M))

The time complexity consists of three main components:

1. Binary search range: The binary search is performed on the range [0, 10^11), which takes O(log(10^11)) iterations. Since we're looking for the k-th smallest value that can be formed by multiples of coins, and the maximum coin value is M, the actual search range is approximately O(log(k × M)).

2. Check function per binary search iteration: For each binary search iteration, the check function is called, which:

   • Iterates through all possible subsets of coins: 2^n subsets (from 1 to 2^n - 1)
   • For each subset, computes the LCM of selected coins, which takes O(n) time in the worst case (iterating through all coins when all bits are set)
   • The LCM calculation itself has a cost, but it's dominated by the iteration through coins

3. Overall: Combining these factors: O(log(k × M)) binary search iterations × O(2^n) subsets × O(n) operations per subset = O(n × 2^n × log(k × M))

Space Complexity: O(1)

The space complexity is constant as the algorithm only uses:

• A few integer variables (cnt, v, m, i, j)
• No additional data structures that scale with input size
• The recursive calls in bisect_left use O(log(k × M)) stack space, but this is typically considered negligible compared to the dominant factors

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Problem Constraint

The most critical pitfall is misinterpreting what amounts can be formed. Many people initially think this is a standard coin change problem where you can mix different denominations (e.g., using one coin of value 3 and one coin of value 5 to make 8). However, the constraint explicitly states you can only use multiple coins of the same denomination for any given amount.

Wrong interpretation: With coins = [3, 5], thinking you can make 8 (3 + 5) Correct interpretation: You cannot make 8 because it requires mixing denominations

2. Incorrect Inclusion-Exclusion Logic

A common mistake is getting the inclusion-exclusion signs backwards:

# WRONG - Signs are reversed!
if subset_size & 1:  # Odd size
    total_count -= max_value // lcm_value  # Should be ADD
else:  # Even size
    total_count += max_value // lcm_value  # Should be SUBTRACT

Solution: Remember that inclusion-exclusion starts with adding single elements (odd-sized subsets) and subtracting their intersections (even-sized subsets).

3. LCM Overflow Not Handled Properly

The LCM can grow very large, potentially exceeding the search bounds:

# WRONG - No overflow check
for coin_index, coin_value in enumerate(coins):
    if subset_mask >> coin_index & 1:
        lcm_value = lcm(lcm_value, coin_value)
        # Missing: if lcm_value > max_value: break

Without the overflow check, you might:

• Waste computation on LCMs that are already too large
• Risk integer overflow in extreme cases

Solution: Always check if lcm_value > max_value: break after computing each LCM step.

4. Incorrect Binary Search Bounds

Using too small an upper bound for binary search:

# WRONG - Upper bound too small
return bisect_left(range(10**6), True, key=count_multiples_up_to)

With k potentially being up to 10^9 and coins as small as 1, the k-th smallest value could be quite large.

Solution: Use a sufficiently large upper bound like 10**11 to ensure the answer falls within the search range.

5. Off-by-One Error in Binary Search

Confusing when to use bisect_left vs bisect_right:

# WRONG - Using bisect_right when we need the first valid position
return bisect_right(range(10**11), True, key=count_multiples_up_to)

Since we want the smallest value where the count is at least k, we need bisect_left to find the leftmost position where the condition becomes true.

6. Not Understanding Why This Approach Works

Many might wonder why we're counting multiples using inclusion-exclusion instead of generating and sorting all possible amounts. The key insight is that:

• We're counting how many valid amounts exist up to a given value
• Binary search finds the exact value where this count equals k
• This avoids explicitly generating all amounts, which would be inefficient

Example to clarify: With coins = [3, 5] and checking up to 10:

• Multiples of 3: {3, 6, 9} → count = 3
• Multiples of 5: {5, 10} → count = 2
• Multiples of lcm(3,5)=15: {} → count = 0
• Total using inclusion-exclusion: 3 + 2 - 0 = 5 valid amounts ≤ 10