Kth Distinct Amount Using One Denomination
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
# Kth Distinct Amount Using One Denomination
You are given distinct coin denominations in `coins` and a positive integer `k`. An unlimited number of coins of each denomination is available.
Each amount must use one denomination only. You may use any positive number of coins of that denomination, but you cannot mix different denominations within one amount.
Consider all distinct positive amounts that can be made, sorted from smallest to largest. Return the `k`th amount, using one-based ranking. If several denominations can make the same amount, that amount appears only once in the ranking.
### Examples
**Example 1**
```text
Input: coins = [4,6], k = 6
Output: 18
```
The first six distinct valid amounts are `4,6,8,12,16,18`. Amount 12 counts once although either denomination can make it. Amount 10 does not qualify: making it as `4 + 6` would mix denominations.
**Example 2**
```text
Input: coins = [2,4,7], k = 8
Output: 14
```
The first eight amounts are `2,4,6,7,8,10,12,14`. The denomination four does not add a new amount beyond those already made with denomination two. Amount 14 is counted once even though both twos and sevens can make it.
### Constraints
- `1 <= coins.length <= 15`.
- `1 <= coins[i] <= 25`.
- `1 <= k <= 2 * 10^9`.
- All denominations in `coins` are pairwise distinct.
### Clarifying Questions
- Is zero part of the ranking? No; rank positive amounts made with at least one coin.
- Can different denominations be combined to reach a new amount? No.
- Are different ways to make one amount ranked separately? No; rank distinct amounts.
- Can one denomination be a multiple of another? Yes; distinct does not forbid divisibility.
- Is the input necessarily sorted? No such guarantee is given.
### C++ Interface
```cpp
class Solution {
public:
long long findKthSmallest(vector<int>& coins, int k) {
}
};
```
### Reasoning Checkpoints
- Rank distinct positive amounts while enforcing the single-denomination restriction.
- Account for overlap between denominations and preserve one-based ranking.
- Justify correctness, termination, resource use and wide arithmetic for the largest `k`.
```hint Count amounts below a candidate limit
An amount is valid when at least one denomination divides it. Inclusion-exclusion over denomination subsets counts distinct valid amounts up to a limit; a subset's overlap consists of multiples of its least common multiple. Use this count to locate the first limit containing at least k valid amounts.
```
Overview: Find the kth distinct positive amount made with one coin denomination at a time, counting overlaps once and supporting a large rank.