3116. Kth Smallest Amount With Single Denomination Combination

Array
Binary Search
Bit Manipulation
Math
Number Theory
Combinatorics

TIME

O(2^m log(k minCoin))

SPACE

O(2^m)

Intuition

Since denominations can't be mixed, coin c produces exactly the multiples of c. The set of reachable amounts is therefore the union of the multiple-sets of all coins.

k reaches 2 * 10^9, so the amounts can't be enumerated. But the number of reachable amounts <= x is easy to compute in closed form, and it's monotone non-decreasing in x so binary search the smallest x whose count reaches k.

Counting the union needs inclusion-exclusion, because a value like 6 is counted by both coin 2 and coin 3. An amount is divisible by every coin in a subset S exactly when it's a multiple of lcm(S), giving:

count(x) = sum over non-empty S of  (-1)^(|S|+1) * floor(x / lcm(S))

Approach

Prune redundant coins. If coin c is a multiple of another coin d, every multiple of c is already a multiple of d, so c contributes nothing. ([3,6,9] collapses to [3].) This matters a lot, the largest possible surviving set is an antichain under divisibility, which for values 1..25 is at most 13 coins, capping the subsets at 2^13 instead of 2^15.
Search bound. The smallest coin alone already yields k multiples by k * min(coin), so that's a valid upper bound (at most 5 * 10^10).
Precompute subset LCMs once, pairing each with its inclusion-exclusion sign. Any subset whose LCM exceeds the upper bound contributes floor(x / lcm) = 0 for every candidate x, so drop it during precomputation (this also stops the LCM from overflowing).
Binary search x in [1, k * min(coin)] for the smallest value with count(x) >= k.

Complexity

Time: O(2^m * log(k * minCoin)) where m <= 13 is the pruned coin count, about 8191 * 36 ≈ 3 * 10^5 operations
Space: O(2^m), the precomputed LCM/sign terms

Edge Cases

A coin equal to 1 makes every integer reachable → answer is exactly k
Single coin c → answer is c * k (up to 25 * 2 * 10^9 = 5 * 10^10)
Coins that are multiples of one another (Example 1) → pruned away entirely
The answer exceeds 32-bit (up to 5 * 10^10), so the return type and all intermediates must be long
LCMs can overflow if computed unguarded; cap them against the search bound

Code

from typing import List
from math import gcd


class Solution:
    def findKthSmallest(self, coins: List[int], k: int) -> int:
        """
        3116. Kth Smallest Amount With Single Denomination Combination
        Time: O(2^m * log(k * minCoin))
        Space: O(2^m)
        """
        # Drop coins that are multiples of another coin: their multiples
        # are already covered, so they add nothing to the union.
        base = []
        for c in sorted(coins):
            if not any(c % d == 0 for d in base):
                base.append(c)

        n = len(base)
        hi = k * base[0]  # smallest coin alone reaches k multiples by here

        # Inclusion-exclusion terms: (lcm, sign). Subsets whose lcm exceeds
        # hi always contribute 0, so they are skipped (also avoids overflow).
        terms = []
        for mask in range(1, 1 << n):
            lcm = 1
            for i in range(n):
                if mask >> i & 1:
                    lcm = lcm // gcd(lcm, base[i]) * base[i]
                    if lcm > hi:
                        break
            else:
                sign = 1 if bin(mask).count("1") % 2 else -1
                terms.append((lcm, sign))

        def count(x: int) -> int:
            # how many reachable amounts are <= x
            return sum(sign * (x // lcm) for lcm, sign in terms)

        lo = 1
        while lo < hi:
            mid = (lo + hi) // 2
            if count(mid) >= k:
                hi = mid
            else:
                lo = mid + 1
        return lo

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 3116. Kth Smallest Amount With Single Denomination Combination
 * Time: O(2^m * log(k * minCoin))
 * Space: O(2^m)
 */
class Solution {
    public long findKthSmallest(int[] coins, int k) {
        // Drop coins that are multiples of another coin: their multiples
        // are already covered, so they add nothing to the union.
        int[] sorted = coins.clone();
        Arrays.sort(sorted);
        List<Integer> base = new ArrayList<>();
        for (int c : sorted) {
            boolean redundant = false;
            for (int d : base) {
                if (c % d == 0) {
                    redundant = true;
                    break;
                }
            }
            if (!redundant) {
                base.add(c);
            }
        }

        int n = base.size();
        long hi = (long) k * base.get(0); // smallest coin alone reaches k multiples by here

        // Inclusion-exclusion terms: lcm paired with sign. Subsets whose lcm
        // exceeds hi always contribute 0, so they are skipped (avoids overflow).
        List<long[]> terms = new ArrayList<>();
        for (int mask = 1; mask < (1 << n); mask++) {
            long lcm = 1;
            boolean keep = true;
            for (int i = 0; i < n; i++) {
                if ((mask >> i & 1) == 1) {
                    lcm = lcm / gcd(lcm, base.get(i)) * base.get(i);
                    if (lcm > hi) {
                        keep = false;
                        break;
                    }
                }
            }
            if (keep) {
                long sign = (Integer.bitCount(mask) % 2 == 1) ? 1 : -1;
                terms.add(new long[]{lcm, sign});
            }
        }

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

    /** How many reachable amounts are <= x. */
    private long count(List<long[]> terms, long x) {
        long total = 0;
        for (long[] t : terms) {
            total += t[1] * (x / t[0]);
        }
        return total;
    }

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