#3116

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Kth Smallest Amount With Single Denomination Combination

Find the kth smallest amount using only one coin denomination at a time, applying binary search efficiently over possible sums.

array math binary search bit manipulation combinatorics

Problem Statement

Given an array of distinct integers coins representing coin denominations and an integer k, find the kth smallest amount that can be formed using only one type of coin per sum. You cannot combine different denominations in a single sum, but each coin has infinite supply.

Return the kth smallest amount obtainable by these rules. For example, if coins = [3,6,9] and k = 3, the amounts are 3, 6, 9, 9, 12, 12, 15, 15, 18, and so on, counting repeated amounts only once per value. Identify the kth smallest in this sequence.

Examples

Example 1

Input: coins = [3,6,9], k = 3

Output: 9

The given coins can make the following amounts: Coin 3 produces multiples of 3: 3, 6, 9, 12, 15, etc. Coin 6 produces multiples of 6: 6, 12, 18, 24, etc. Coin 9 produces multiples of 9: 9, 18, 27, 36, etc. All of the coins combined produce: 3, 6, 9 , 12, 15, etc.

Example 2

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

Output: 12

The given coins can make the following amounts: Coin 5 produces multiples of 5: 5, 10, 15, 20, etc. Coin 2 produces multiples of 2: 2, 4, 6, 8, 10, 12, etc. All of the coins combined produce: 2, 4, 5, 6, 8, 10, 12 , 14, 15, etc.

Constraints

1 <= coins.length <= 15
1 <= coins[i] <= 25
1 <= k <= 2 * 109
coins contains pairwise distinct integers.

Solution Approach

Binary Search the Answer Space

Set low as the smallest coin and high as k times the largest coin. At each step, calculate mid and count how many amounts are <= mid by summing floor(mid / coin) for each coin. Adjust low or high until low meets high to locate the kth smallest amount.

Counting Multiples Efficiently

Instead of generating all multiples, compute how many multiples of each coin are less than or equal to a candidate mid. Summing these counts ensures we accurately determine whether mid reaches at least k sums, which is critical to the binary search pattern of this problem.

Handling Large k Values

Since k can be very large, directly storing all multiples is impractical. Using the counting approach with binary search avoids memory issues and reduces time complexity, fitting perfectly with this problem's single-denomination combination pattern.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log(k * maxCoin)) because each binary search step counts multiples for n coins. Space complexity is O(1) beyond input storage since no extra arrays are needed.

What Interviewers Usually Probe

Check whether you can count multiples without generating sequences explicitly.
They may hint at binary searching over possible sums rather than coin indices.
Expect questions about handling k up to 2 billion efficiently.

Common Pitfalls or Variants

Common pitfalls

Mistakenly combining different coin denominations in a sum, violating the problem constraints.
Generating all multiples up to k, causing memory overflow and slow execution.
Failing to handle duplicate sums correctly when different coins produce the same amount.

Follow-up variants

Find kth largest amount instead of smallest using single-denomination multiples.
Allow combining at most two denominations per sum while maintaining a large k.
Restrict coin denominations to prime numbers only, testing counting efficiency.

FAQ

What is the main pattern used in Kth Smallest Amount With Single Denomination Combination?

The main pattern is binary search over the valid answer space combined with counting multiples of each coin.

Can I combine different coin denominations in this problem?

No, each sum must use only a single coin denomination, with infinite supply per coin.

How do I handle very large k values efficiently?

Use binary search over the answer space and count multiples instead of generating all sums.

What is the time complexity of the solution?

Time complexity is O(n log(k * maxCoin)), iterating n coins for each binary search step.

How do I avoid counting duplicates incorrectly?

Count each multiple once per coin, and sum these counts without merging sequences to maintain correctness.

terminal

Solution

Solution 1: Binary Search + Inclusion-Exclusion Principle

We can transform the problem into: find the smallest positive integer $x$ such that the number of numbers less than or equal to $x$ and satisfying the condition is exactly $k$. If $x$ satisfies the condition, then for any $x' > x$, $x'$ also satisfies the condition. This shows monotonicity, so we can use binary search to find the smallest $x$ that satisfies the condition.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def findKthSmallest(self, coins: List[int], k: int) -> int:
        def check(mx: int) -> bool:
            cnt = 0
            for i in range(1, 1 << len(coins)):
                v = 1
                for j, x in enumerate(coins):
                    if i >> j & 1:
                        v = lcm(v, x)
                        if v > mx:
                            break
                m = i.bit_count()
                if m & 1:
                    cnt += mx // v
                else:
                    cnt -= mx // v
            return cnt >= k

        return bisect_left(range(10**11), True, key=check)

Continue Practicing

#3312 sorted gcd pair queries #3444 minimum increments for target multiples in an array #3539 find sum of array product of magical sequences