# Kth Smallest Amount With Single Denomination Combination
**Difficulty:** HARD
[External](https://leetcode.com/problems/kth-smallest-amount-with-single-denomination-combination)
Canonical: https://scaleengineer.com/dsa/problems/kth-smallest-amount-with-single-denomination-combination
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
---
## Problem
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.

# Approaches
## Simulation using a Min-Heap
This approach simulates the process of generating amounts in increasing order. We use a min-heap (Priority Queue in Java) to efficiently keep track of and retrieve the next smallest amount that can be formed from the multiples of all coins. This can be visualized as merging `N` sorted lists, where `N` is the number of coins.
**Time:** O(k * N * log N). In the worst case, we might have to perform close to `k * N` poll operations from the heap due to duplicate amounts. Each heap operation takes `O(log N)` time. This is too slow for the given constraints on `k`. · **Space:** O(N), where N is the number of coins. The priority queue stores at most N elements at any time (one for each coin's stream of multiples).
**Pros:** Conceptually simpler and more intuitive than the optimal mathematical approach.; Relatively easy to implement if familiar with priority queues.
**Cons:** The time complexity is proportional to `k`, which is too slow for the given constraints where `k` can be up to `2 * 10^9`.; This approach will likely result in a 'Time Limit Exceeded' error on platforms with strict time limits.
### Explanation
The core idea is to treat the multiples of each coin as a sorted stream of numbers. We want to find the `k`-th smallest element from the union of these streams. A min-heap is the perfect data structure for this 'merging' operation.

We initialize the heap with the first multiple of each coin (the coin values themselves). Then, we repeatedly extract the minimum element from the heap. This element is the next smallest amount in the combined sequence. To handle cases where the same amount can be generated by different coins (e.g., 12 is a multiple of 3, 6), we only increment our count for new, unique amounts. After processing an amount `m` generated by a coin `c`, we add the next multiple, `m + c`, into the heap. We continue this process until we have found `k` unique amounts.

```java
import java.util.*;

class Solution {
    public long kthSmallestAmount(int[] coins, int k) {
        // This approach is too slow for the given constraints but illustrates the idea.
        // It would work for smaller k.
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        
        // Pre-filtering coins can be an optimization but doesn't change the main complexity issue with large k.
        // For simplicity, we'll use all coins.
        for (int coin : coins) {
            pq.offer(new long[]{coin, coin});
        }

        long lastAmount = -1;
        int count = 0;

        while (!pq.isEmpty()) {
            long[] current = pq.poll();
            long currentAmount = current[0];
            long originalCoin = current[1];

            if (currentAmount > lastAmount) {
                count++;
                lastAmount = currentAmount;
                if (count == k) {
                    return currentAmount;
                }
            }
            
            // Add the next multiple, checking for overflow
            if (Long.MAX_VALUE - originalCoin >= currentAmount) {
                 pq.offer(new long[]{currentAmount + originalCoin, originalCoin});
            }
        }
        
        return -1; // Should not be reached
    }
}
```
### Algorithm
*   **Preprocessing (Optional but Recommended):** Filter the `coins` array to remove any coin `c1` that is a multiple of another coin `c2` in the array. This is because any amount that is a multiple of `c1` is also a multiple of `c2`, so `c1` is redundant.
*   **Initialization:** Create a min-priority queue to store arrays of `[amount, original_coin]`. For each non-redundant coin, add `[coin, coin]` to the priority queue.
*   **Iteration:** Maintain a count of unique amounts found and the value of the last unique amount processed (`last_amount`).
*   **Main Loop:** Repeatedly extract the element with the smallest amount from the priority queue.
    *   If the extracted `current_amount` is the same as `last_amount`, it's a duplicate (e.g., 6 from coin 2 and 6 from coin 3). We ignore it but still process its next multiple.
    *   If `current_amount` is greater than `last_amount`, it's a new unique amount. Increment the `count` and update `last_amount`.
    *   If `count` reaches `k`, we have found our answer.
    *   Add the next multiple, `[current_amount + original_coin, original_coin]`, back into the priority queue.

## Binary Search on the Answer with Inclusion-Exclusion
This highly efficient approach leverages the monotonic property of the problem: if an amount `M` has `c` valid amounts less than or equal to it, any amount `M' > M` will have at least `c` amounts. This allows us to binary search for the `k`-th smallest amount. The main challenge is to create a function that, for any given amount `X`, can count how many valid amounts are less than or equal to `X`. This counting problem is solved using the Principle of Inclusion-Exclusion (PIE).
**Time:** O(N^2 + log(R) * 2^N * log(M)). `N` is the number of coins (`<=15`), `R` is the binary search range (up to `k * C_min`), and `M` is a value in that range. `N^2` is for preprocessing. `log(R)` is for binary search iterations. `2^N` is for iterating through subsets for PIE. `log(M)` is for the GCD calculation within the LCM. This is efficient enough to pass. · **Space:** O(N), where N is the number of coins. This space is used to store the filtered coins and for the recursion stack if PIE is implemented recursively. The iterative implementation also has minimal space overhead.
**Pros:** Extremely efficient and scalable for large values of `k`.; The time complexity does not depend on `k`, but rather on the number of coins `N`.; Optimal solution for the given constraints.
**Cons:** More complex to understand and implement correctly compared to a direct simulation.; Requires careful handling of the Principle of Inclusion-Exclusion logic.; LCM calculations for many numbers can lead to very large values, requiring `long` and checks for overflow.
### Explanation
The search space for the answer can be huge, but we can efficiently find the `k`-th amount by binary searching on the value of the amount itself. For any candidate amount `M`, we need to determine its rank, i.e., how many unique amounts are less than or equal to `M`. Let's call this function `countLe(M)`.

If `countLe(M) < k`, `M` is too small, and we must search for a larger amount. If `countLe(M) >= k`, `M` could be our answer, or the answer could be even smaller. This is the standard binary search pattern for finding the minimum value that satisfies a condition.

The `countLe(M)` function is the heart of this solution. The total number of amounts less than or equal to `M` is the size of the union of the sets of multiples for each coin. This is calculated using the Principle of Inclusion-Exclusion.

`countLe(M) = Σ floor(M/c_i) - Σ floor(M/lcm(c_i, c_j)) + Σ floor(M/lcm(c_i, c_j, c_k)) - ...`

We can implement this by iterating through all `2^n - 1` non-empty subsets of the coins. For each subset, we compute the LCM of the coins within it and add or subtract `M / LCM` based on the subset's size.

```java
import java.util.*;

class Solution {
    public long kthSmallestAmount(int[] coins, int k) {
        int n = coins.length;
        List<Integer> uniqueCoins = new ArrayList<>();
        Arrays.sort(coins);
        for (int i = 0; i < n; i++) {
            boolean isRedundant = false;
            for (int j = 0; j < i; j++) {
                if (coins[i] % coins[j] == 0) {
                    isRedundant = true;
                    break;
                }
            }
            if (!isRedundant) {
                uniqueCoins.add(coins[i]);
            }
        }

        int[] filteredCoins = uniqueCoins.stream().mapToInt(i -> i).toArray();
        n = filteredCoins.length;

        long low = 1;
        long high = (long) k * filteredCoins[0]; 
        long ans = high;

        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (countLe(mid, filteredCoins) >= k) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    private long countLe(long m, int[] coins) {
        int n = coins.length;
        long count = 0;
        for (int i = 1; i < (1 << n); i++) {
            long currentLcm = 1;
            int subsetSize = 0;
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) {
                    subsetSize++;
                    currentLcm = lcm(currentLcm, coins[j]);
                    if (currentLcm > m) { // Optimization
                        currentLcm = m + 1;
                        break;
                    }
                }
            }

            if (currentLcm <= m) {
                if (subsetSize % 2 == 1) {
                    count += m / currentLcm;
                } else {
                    count -= m / currentLcm;
                }
            }
        }
        return count;
    }

    private long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    private long lcm(long a, long b) {
        if (a == 0 || b == 0) return 0;
        // Check for overflow before multiplication
        if (a > Long.MAX_VALUE / b) return Long.MAX_VALUE;
        long res = a * b / gcd(a, b);
        return res;
    }
}
```
### Algorithm
*   **Preprocessing:** As an optimization, filter the `coins` array. A coin `c1` is redundant if it's a multiple of another coin `c2`. Removing these can reduce `n` and speed up the PIE calculation.
*   **Binary Search Setup:** Define a search range for the answer. A safe range is `[1, k * min_coin]`, as the `k`-th amount cannot be larger than the `k`-th multiple of the smallest coin.
*   **Binary Search Loop:**
    *   Pick a `mid` value in the current search range.
    *   Calculate `count = countLe(mid)`, which is the number of unique amounts less than or equal to `mid`.
    *   If `count >= k`, it means `mid` is a potential answer, and the actual answer could be `mid` or something smaller. So, we record `mid` and shrink the search space to the lower half: `high = mid - 1`.
    *   If `count < k`, `mid` is too small. The answer must be larger. We search in the upper half: `low = mid + 1`.
*   **`countLe(M)` Function (PIE):**
    *   This function calculates `|U S_i|` where `S_i` are multiples of `coins[i]` up to `M`.
    *   Iterate through all `2^n - 1` non-empty subsets of the (filtered) coins.
    *   For each subset, calculate the Least Common Multiple (LCM) of its elements. Be careful to handle potential `long` overflows during LCM calculation. If the LCM exceeds `M`, its contribution is zero.
    *   If the subset size is odd, add `M / lcm` to the total count.
    *   If the subset size is even, subtract `M / lcm` from the total count.
*   **Return Value:** The binary search terminates when `low > high`, and the last recorded potential answer is the `k`-th smallest amount.

# Solutions
### Java

```java
class Solution {
private
  int[] coins;
private
  int k;
public
  long findKthSmallest(int[] coins, int k) {
    this.coins = coins;
    this.k = k;
    long l = 1, r = (long)1 e11;
    while (l < r) {
      long mid = (l + r) >> 1;
      if (check(mid)) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
private
  boolean check(long mx) {
    long cnt = 0;
    int n = coins.length;
    for (int i = 1; i < 1 << n; ++i) {
      long v = 1;
      for (int j = 0; j < n; ++j) {
        if ((i >> j & 1) == 1) {
          v = lcm(v, coins[j]);
          if (v > mx) {
            break;
          }
        }
      }
      int m = Integer.bitCount(i);
      if (m % 2 == 1) {
        cnt += mx / v;
      } else {
        cnt -= mx / v;
      }
    }
    return cnt >= k;
  }
private
  long lcm(long a, long b) { return a * b / gcd(a, b); }
private
  long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }
}

```

### CPP

```cpp
class Solution {
public:
  long long findKthSmallest(vector<int> &coins, int k) {
    using ll = long long;
    ll l = 1, r = 1e11;
    int n = coins.size();
    auto check = [&](ll mx) {
      ll cnt = 0;
      for (int i = 1; i < 1 << n; ++i) {
        ll v = 1;
        for (int j = 0; j < n; ++j) {
          if (i >> j & 1) {
            v = lcm(v, coins[j]);
            if (v > mx) {
              break;
            }
          }
        }
        int m = __builtin_popcount(i);
        if (m & 1) {
          cnt += mx / v;
        } else {
          cnt -= mx / v;
        }
      }
      return cnt >= k;
    };
    while (l < r) {
      ll mid = (l + r) >> 1;
      if (check(mid)) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
};

```

### Python

```python
class Solution:
    def findKthSmallest(self, coins: List[int], k: int) -> int: def check(mx: int) -> bool: cnt = 0 for i in range(1, 1 << len(coins)): v = 1 for j, x in enumerate(coins): if i >> j & 1: v = lcm(v, x) if v > mx: break m = i . bit_count() if m & 1: cnt += mx // v else: cnt -= mx // v return cnt >= k return bisect_left(range(10 ** 11), True, key=check)

```