Skip to main content
Talentd

Kth Smallest Amount With Single Denomination Combination - Solution & Explanation

HardArrayMathBinary SearchBit Manipulation19 min read
Practice this problem

Problem Statement

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 <= 15
  • 1 <= coins[i] <= 25
  • 1 <= k <= 2 * 109
  • coins contains pairwise distinct integers.

Approach Overview

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.

Approach 1: Min-Heap Approach for Multiples

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

Approach 2: Mathematical Counting

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.

Code

PythonJava

Python

Java

Complexity

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

Try this approach in the editor →

Approach 3: 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.

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 check function. If check(mid) is true, then we update the right boundary r 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Min-Heap Approach for Multiples

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.

Mathematical Counting

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

Binary Search + Inclusion-Exclusion Principle—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Min-Heap for MultiplesO(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 CountingO(2^n log R)O(1)Best for large k or large numeric ranges where generating values directly would be too slow.

Video Solution

3116. Kth Smallest | Math | Inclusion Exclusion | Binary Search | Bitmasking | Bit Manipulation • Aryan Mittal • 7,868 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Kth Smallest Amount With Single Denomination Combination easy or hard?
LeetCode classifies this problem as Hard because it combines several advanced ideas: binary search on the answer, inclusion–exclusion counting, LCM calculations, and subset enumeration with bit manipulation. Recognizing that direct generation is inefficient is the main challenge.
Kth Smallest Amount With Single Denomination Combination Python/Java solution
Both Python and Java implementations typically follow the binary-search strategy. The key components are computing LCM using GCD, iterating over subsets with bit masks, and counting how many multiples fall below the mid value during binary search.
How to solve Kth Smallest Amount With Single Denomination Combination in O(log R)?
Binary search over the answer range and use a counting function to determine how many valid amounts are ≤ x. The counting step applies inclusion–exclusion with LCM across subsets of denominations to avoid double counting. Each iteration narrows the search interval until the smallest value with at least k valid amounts is found.
What is the best approach for Kth Smallest Amount With Single Denomination Combination?
The most efficient approach uses binary search combined with inclusion–exclusion counting. Instead of generating multiples directly, you binary search a candidate value x and count how many numbers ≤ x are divisible by at least one denomination. Inclusion–exclusion with LCM handles overlaps between denominations. This reduces the problem to O(2^n log R) time.
Is Kth Smallest Amount With Single Denomination Combination asked at Google/Amazon/Meta?
Problems involving binary search on the answer combined with number theory or inclusion–exclusion frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of k-th smallest sequence generation and counting multiples are common in senior-level algorithm rounds.
What data structure is used in Kth Smallest Amount With Single Denomination Combination?
Two main techniques appear. A min-heap can merge multiples from different denominations similarly to merging sorted lists. The optimal solution relies more on math and algorithms: binary search, LCM/GCD computations, and bitmask enumeration for inclusion–exclusion.
What is the time complexity of Kth Smallest Amount With Single Denomination Combination?
The optimal binary-search solution runs in O(2^n log R), where n is the number of denominations and R is the search range of possible amounts. Each binary-search step computes counts using inclusion–exclusion across all subsets. A simpler heap-based approach takes O(k log n) time because it generates multiples sequentially.

Ready to solve this problem?

Practice Kth Smallest Amount With Single Denomination Combination with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find the Number of Possible Ways for an Event

Next

Kth Smallest Number in Multiplication Table