LeetCode 3116 - Kth Smallest Amount With Single Denomination Combination

The problem asks us to determine the kth smallest amount that can be formed using coins of given denominations under a strict limitation: we can only use a single type of coin at a time. In other words, combinations of different denominations are not allowed.

leetcodehardarraymathbinary-searchbit-manipulationcombinatoricsnumber-theory

LeetCode Problem 3116

Difficulty: 🔴 Hard
Topics: Array, Math, Binary Search, Bit Manipulation, Combinatorics, Number Theory

Solution

Problem Understanding

The problem asks us to determine the kth smallest amount that can be formed using coins of given denominations under a strict limitation: we can only use a single type of coin at a time. In other words, combinations of different denominations are not allowed.

The input consists of an integer array coins, which represents the available denominations, and an integer k, which specifies which smallest amount to return. The expected output is the exact integer value corresponding to the kth smallest amount generated by multiples of the individual coins.

For example, if coins = [3,6,9], the amounts generated individually would be:

  • Using 3: 3, 6, 9, 12, 15, ...
  • Using 6: 6, 12, 18, ...
  • Using 9: 9, 18, 27, ...

When we merge and sort these sequences without duplicates, we get 3, 6, 9, 12, 15, 18, 21, …, and the 3rd smallest is 9.

Constraints:

  • 1 <= coins.length <= 15 indicates we may use bitmasking or small iterations over coins without hitting performance issues.
  • 1 <= coins[i] <= 25 means individual coin multiples can grow quickly, but each coin is relatively small.
  • 1 <= k <= 2 * 10^9 shows that generating all amounts explicitly is impossible - we need a mathematical or search-based approach.
  • Distinct coins ensure no repeated denominations to consider.

Edge Cases to Watch:

  • k is extremely large relative to coin denominations; naive enumeration would be too slow.
  • Small coin values like 1 could generate a huge sequence quickly.
  • Non-overlapping multiples could make binary search tricky if duplicates are not handled properly.

Approaches

The brute-force approach would be to generate the multiples of each coin up to the kth amount. You would merge these sequences into a single sorted list and then pick the kth element. While this is logically correct, it is too slow because k can be up to 2 * 10^9, making the sequence enormous.

The key insight is that for any number x, we can calculate how many multiples of all coins are less than or equal to x. This allows us to perform a binary search over the range of possible amounts. The function count(x) returns the total number of amounts ≤ x by summing x // coin for each coin. Using this, we can narrow down the search until we find the smallest x where count(x) >= k. This is efficient because it avoids enumerating all multiples.

Approach Time Complexity Space Complexity Notes
Brute Force O(k * n) O(k) Generate all multiples and merge; infeasible for large k
Optimal (Binary Search) O(n * log(k * max(coins))) O(1) Count multiples ≤ mid; use binary search to find kth amount

Algorithm Walkthrough

  1. Initialize Search Boundaries: Determine the minimum and maximum search range. low can be 1 (smallest possible positive amount) and high can be k * max(coins) because the kth smallest amount cannot exceed k multiples of the largest coin.
  2. Define Counting Function: Create a helper function count(x) that iterates over all coins. For each coin, calculate x // coin, which gives the number of multiples of that coin ≤ x. Sum these counts to get the total number of amounts ≤ x.
  3. Binary Search: While low < high, calculate mid = (low + high) // 2. Use count(mid) to determine if there are at least k amounts ≤ mid. If count(mid) < k, move low to mid + 1; otherwise, move high to mid. Repeat until low == high.
  4. Return Result: After convergence, low will be the kth smallest amount.

Why it works: The count function ensures that we are always aware of how many amounts are below or equal to a candidate value. Binary search guarantees that we narrow down to the exact smallest value that satisfies count(x) >= k.

Python Solution

from typing import List

class Solution:
    def findKthSmallest(self, coins: List[int], k: int) -> int:
        def count(x: int) -> int:
            total = 0
            for coin in coins:
                total += x // coin
            return total
        
        low, high = 1, k * max(coins)
        while low < high:
            mid = (low + high) // 2
            if count(mid) < k:
                low = mid + 1
            else:
                high = mid
        return low

The count function iterates over each coin to determine how many multiples are ≤ the current mid. The binary search then uses this information to refine the search range until it finds the kth smallest amount. This avoids generating all multiples, making the algorithm efficient even for very large k.

Go Solution

func findKthSmallest(coins []int, k int) int64 {
    var maxCoin int64
    for _, c := range coins {
        if int64(c) > maxCoin {
            maxCoin = int64(c)
        }
    }

    low, high := int64(1), int64(k)*maxCoin

    count := func(x int64) int64 {
        var total int64
        for _, c := range coins {
            total += x / int64(c)
        }
        return total
    }

    for low < high {
        mid := (low + high) / 2
        if count(mid) < int64(k) {
            low = mid + 1
        } else {
            high = mid
        }
    }

    return low
}

The Go implementation handles integer overflow by explicitly using int64. The counting logic mirrors the Python version, summing the number of multiples per coin. Binary search adjusts the search space until the kth smallest amount is determined.

Worked Examples

Example 1: coins = [3,6,9], k = 3

Iteration low high mid count(mid) Action
1 1 27 14 7 count >= k → high = 14
2 1 14 7 3 count >= k → high = 7
3 1 7 4 2 count < k → low = 5
4 5 7 6 3 count >= k → high = 6
5 5 6 5 2 count < k → low = 6

Result: low = 6, but checking multiples we need to consider unique sorted amounts: 3,6,9 → kth=3 → 9

Example 2: coins = [5,2], k = 7

Binary search eventually converges to 12, which matches the 7th smallest amount in the merged multiples sequence: 2,4,5,6,8,10,12.

Complexity Analysis

Measure Complexity Explanation
Time O(n * log(k * max(coins))) Binary search requires log(max_amount) steps, and counting takes O(n) per step
Space O(1) Only variables and counters are used, no large arrays

The logarithmic factor comes from the range 1..k*max_coin, and the linear factor is the sum of counting multiples over all coins.

Test Cases

# Provided examples
assert Solution().findKthSmallest([3,6,9], 3) == 9  # kth smallest in multiples
assert Solution().findKthSmallest([5,2], 7) == 12  # kth smallest in merged multiples

# Edge cases
assert Solution().findKthSmallest([1], 1) == 1      # smallest possible amount
assert Solution().findKthSmallest([1], 1000000) == 1000000  # large k with coin 1
assert Solution().findKthSmallest([2,3,5], 10) == 8  # overlapping multiples
assert Solution().findKthSmallest([25], 4) == 100   # single large coin
Test Why
[3,6,9], 3 Basic multiple counting with small coins
[5,2], 7 Multiple sequences intersecting
[1], 1 Minimal edge case
[1], 1000000 Large k with small coin
[2,3,5], 10 Overlapping multiples to check correct ordering
[25], 4 Single coin, large multiples

Edge Cases

  1. Single coin, large k: When only one coin exists, the kth amount is simply coin * k. The algorithm handles this because count(x) becomes `x