You are given an integer array coins representing coins of different denominations and an integer k.
You have an infinite number of coins of each denomination. However, you are not allowed to combine coins of different denominations.
Return the kth smallest amount that can be made using these coins.
Example 1:
Input: coins = [3,6,9], k = 3
Output: 9
Explanation: 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
Explanation: 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 <= 151 <= coins[i] <= 251 <= k <= 2 * 109coins contains pairwise distinct integers.Problem Overview: You are given several coin denominations. You can use only one denomination at a time but any number of coins of that type. Each denomination generates multiples (d, 2d, 3d...). The task is to find the kth smallest amount that appears in the union of all these multiples.
Approach 1: Min-Heap Approach for Multiples (O(k log n) time, O(n) space)
Treat every denomination as an infinite sorted sequence of multiples. Start by pushing the first multiple of each denomination into a min-heap. Repeatedly pop the smallest value, record it if it is not a duplicate, and push the next multiple of the same denomination. A hash set or last-seen value helps avoid counting duplicates when two denominations produce the same amount (for example 6 from 2×3 and 3×2). This approach mirrors merging k sorted lists. It works well when k is moderate, but performance degrades for very large k because you must explicitly generate values one by one.
Approach 2: Mathematical Counting with Binary Search (O(2^n log R) time, O(1) space)
The optimal strategy avoids generating values directly. Instead, binary search the answer x. For each candidate value, compute how many valid amounts are ≤ x. Every denomination contributes x / coin multiples, but overlaps occur when a number is divisible by multiple denominations. Use inclusion–exclusion with LCM to handle overlaps: add counts for single coins, subtract counts for pairs using their LCM, add for triples, and so on. Subsets can be enumerated efficiently using bit manipulation. LCM calculations rely on number theory concepts. Combine this counting function with binary search over the numeric range until the smallest value with at least k valid amounts is found.
The key insight: instead of generating the sequence, compute how many values fall below a threshold. Binary search converts the problem into repeated counting queries, which is dramatically faster when k can reach very large values.
Recommended for interviews: The heap method shows you recognize the problem as merging sorted sequences, which is a solid baseline. Interviewers typically expect the binary-search + inclusion–exclusion approach because it demonstrates stronger algorithmic thinking, familiarity with LCM/GCD math, and efficient counting techniques.
This approach uses a min-heap to efficiently find the k-th smallest amount. We can generate multiples of each coin denomination and insert them into a min-heap, keeping track of the smallest values across all sequences.
The solution initializes a min-heap with each coin denomination. The tuple (coin, coin) is inserted into the heap, where every element is a pair of current_value and the base coin denomination. We repeatedly pop the smallest value from the heap, and after k iterations, the k-th smallest element is returned. After popping, we push the next multiple of that coin into the heap.
Time Complexity: O(k log n), where n is the number of coin denominations.
Space Complexity: O(n), where n is the number of coin denominations.
Another approach is to count numbers that are multiples of any given denomination using mathematics and number theory concepts to find the k-th smallest efficiently. This avoids insertion into a heap by logically deducing the k-th smallest multiple.
This approach uses binary search to find the k-th smallest value by searching over a range of potential answers. For each midpoint in the range, we calculate how many numbers are divisible by each coin denomination and adjust the search region based on whether the count is less than or greater than k.
Time Complexity: O(n log(max * k)), where n is the number of coin denominations and max is the largest denomination.
Space Complexity: O(1).
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.
We define a function check(x) to determine whether the number of numbers less than or equal to x and satisfying the condition is greater than or equal to k. We need to calculate how many numbers can be obtained from the array coins.
Suppose coins = [a, b], according to the inclusion-exclusion principle, the number of numbers less than or equal to x and satisfying the condition is:
$
\left\lfloor \frac{x}{a} \right\rfloor + \left\lfloor \frac{x}{b} \right\rfloor - \left\lfloor \frac{x}{lcm(a, b)} \right\rfloor
If coins = [a, b, c], the number of numbers less than or equal to x and satisfying the condition is:
\left\lfloor \frac{x}{a} \right\rfloor + \left\lfloor \frac{x}{b} \right\rfloor + \left\lfloor \frac{x}{c} \right\rfloor - \left\lfloor \frac{x}{lcm(a, b)} \right\rfloor - \left\lfloor \frac{x}{lcm(a, c)} \right\rfloor - \left\lfloor \frac{x}{lcm(b, c)} \right\rfloor + \left\lfloor \frac{x}{lcm(a, b, c)} \right\rfloor
As you can see, we need to add all cases with an odd number of elements and subtract all cases with an even number of elements.
Since n leq 15, we can use binary enumeration to enumerate all subsets and calculate the number of numbers that satisfy the condition, denoted as cnt. If cnt geq k, then we need to find the smallest x such that check(x) is true.
At the start of the binary search, we define the left boundary l=1 and the right boundary r={10}^{11}. Then we continuously substitute the middle value mid into the rcheck function. If check(mid) is true, then we update the right boundary to mid, otherwise we update the left boundary l to mid+1. Finally, we return l.
The time complexity is O(n times 2^n times log (k times M)), where n is the length of the array coins, and M$ is the maximum value in the array.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Min-Heap Approach for Multiples | Time Complexity: O(k log n), where n is the number of coin denominations. |
| Mathematical Counting | Time Complexity: O(n log(max * k)), where n is the number of coin denominations and max is the largest denomination. |
| Binary Search + Inclusion-Exclusion Principle | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Min-Heap for Multiples | O(k log n) | O(n) | Useful when k is relatively small and you want a straightforward merge of multiple sorted sequences. |
| Binary Search + Inclusion-Exclusion Counting | O(2^n log R) | O(1) | Best for large k or large numeric ranges where generating values directly would be too slow. |
3116. Kth Smallest | Math | Inclusion Exclusion | Binary Search | Bitmasking | Bit Manipulation • Aryan Mittal • 7,766 views views
Watch 3 more video solutions →Practice Kth Smallest Amount With Single Denomination Combination with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor