395. Kth Smallest Amount With Single Denomination Combination

The producible amounts are exactly the numbers divisible by at least one coin. That count is monotonic, so binary search the smallest value whose count reaches k, using inclusion-exclusion over coin subsets to count without enumerating.

Key idea

Because you may not mix denominations, coin c produces exactly its multiples c, 2c, 3c, .... So the full set of reachable amounts is the union of the multiples of every coin — equivalently, every positive integer that is divisible by at least one coin. We want the k-th smallest such number.

Let count(x) = how many reachable amounts are <= x. As x grows, count(x) never decreases — it is monotonic. That is the classic signal to binary search on the answer: find the smallest x with count(x) >= k. That x is the k-th amount (it must itself be reachable, since the count only increases when we land on a reachable value).

Counting with inclusion-exclusion

How many numbers in [1, x] are divisible by at least one coin? Naively summing x / coin_i double counts numbers divisible by several coins. Fix it with inclusion-exclusion over every non-empty subset S of coins:

• add floor(x / lcm(S)) when |S| is odd,
• subtract it when |S| is even,

where lcm(S) is the least common multiple of the coins in S. With n <= 15 coins there are 2^n - 1 <= 32767 subsets, and each subset's (lcm, sign) is precomputed once.

Search bounds

The answer is at most min(coins) * k: the smallest coin alone already yields k distinct multiples ending at min(coins) * k, so the true k-th amount cannot exceed that. Search the range [1, min(coins) * k].

Walk-through: coins = [5, 2], k = 7

Precompute non-empty subsets: {5} -> lcm 5, +, {2} -> lcm 2, +, {5,2} -> lcm 10, -. So count(x) = x/5 + x/2 - x/10.

Search range lo = 1, hi = min(5,2) * 7 = 14.

1. mid = 7: count = 7/5 + 7/2 - 7/10 = 1 + 3 - 0 = 4. 4 < 7 -> too few, go right: lo = 8.
2. mid = 11: count = 11/5 + 11/2 - 11/10 = 2 + 5 - 1 = 6. 6 < 7 -> go right: lo = 12.
3. mid = 13: count = 13/5 + 13/2 - 13/10 = 2 + 6 - 1 = 7. 7 >= 7 -> enough, go left: hi = 13.
4. mid = 12: count = 12/5 + 12/2 - 12/10 = 2 + 6 - 1 = 7. 7 >= 7 -> hi = 12.

Now lo = hi = 12. The reachable amounts are 2,4,5,6,8,10,12,... and the 7th is indeed 12.

Complexity

• Time: O(2^n) to precompute subset LCMs, then O(2^n · log(min(coins)·k)) for the binary search — each count check scans all subsets.
• Space: O(2^n) to store each subset's LCM and sign.

class Solution {
    public long findKthSmallest(int[] coins, int k) {
        int n = coins.length;
        int size = 1 << n;
        long[] lcms = new long[size];
        int[] sign = new int[size];
        for (int mask = 1; mask < size; mask++) {
            long lcm = 1;
            int bits = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    bits++;
                    lcm = lcm / gcd(lcm, coins[i]) * coins[i];
                }
            }
            lcms[mask] = lcm;
            sign[mask] = (bits % 2 == 1) ? 1 : -1;
        }

        int minCoin = coins[0];
        for (int c : coins) minCoin = Math.min(minCoin, c);

        long lo = 1, hi = (long) minCoin * k;
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (count(mid, lcms, sign, size) >= k) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    private long count(long x, long[] lcms, int[] sign, int size) {
        long total = 0;
        for (int mask = 1; mask < size; mask++) {
            total += sign[mask] * (x / lcms[mask]);
        }
        return total;
    }

    private long gcd(long a, long b) {
        while (b != 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
}