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.

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.

Description Hints 2 Solution Video 34:37

3116. Kth Smallest Amount With Single Denomination Combination

Q: 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.

Q: 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.

Hard50.3% acceptance

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 k^th 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 * 10⁹
coins contains pairwise distinct integers.

Topics

Hints open one at a time

Hint 1

Binary search the answer x.

Hint 2

Use the inclusion-exclusion principle to count the number of distinct amounts that can be made up to x.

34:37

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

3116. Kth Smallest Amount With Single Denomination Combination

Topics

Hints open one at a time

Similar problems