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.The key idea is to find the kth smallest amount that can be formed when each amount uses coins of only a single denomination. This means the valid values are simply the multiples of each denomination. The problem therefore reduces to finding the kth smallest number in the union of multiple arithmetic progressions.
A common strategy is to apply binary search on the answer. For a candidate value x, we count how many valid amounts ≤ x exist. Since duplicates can occur when a number is divisible by multiple denominations, we use the inclusion–exclusion principle combined with LCM computations to correctly count unique values. Bit masking is often used to iterate through subsets of denominations when applying inclusion–exclusion.
The binary search narrows the range until we find the smallest value whose count is at least k. This approach efficiently handles very large search spaces while keeping counting manageable.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Binary Search with Inclusion–Exclusion (LCM + Bitmask) | O(2^n * log R) | O(1) |
CrioDo
Use these hints if you're stuck. Try solving on your own first.
Binary search the answer <code>x</code>.
Use the inclusion-exclusion principle to count the number of distinct amounts that can be made up to <code>x</code>.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Multiple denominations can generate the same amount because numbers may be divisible by more than one coin value. Inclusion–exclusion helps avoid double counting by systematically adding and subtracting counts based on LCMs of denomination subsets.
Problems involving kth elements with binary search and inclusion–exclusion are common in advanced technical interviews. While the exact problem may vary, the underlying concepts such as number theory and search over answer space are frequently tested.
The optimal approach uses binary search on the answer combined with the inclusion–exclusion principle. For each candidate value, we count how many numbers are divisible by at least one denomination using LCM calculations. This allows efficient determination of the kth valid amount.
Key concepts include binary search on the answer, number theory (LCM and divisibility), bit manipulation for subset enumeration, and the inclusion–exclusion principle. Understanding how to count multiples efficiently is crucial.