3116. Kth Smallest Amount With Single Denomination Combination

class Solution {
    public long findKthSmallest(int[] coins, int k) {
        int minCoin = coins[0];
        for (int c : coins) {
            minCoin = Math.min(minCoin, c);
        }

        long lo = 1, hi = (long) k * minCoin;

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

        return lo;
    }

    private long countUpTo(long x, int[] coins) {
        int n = coins.length;
        long count = 0;

        for (int mask = 1; mask < (1 << n); mask++) {
            long lcmVal = 1;
            boolean tooBig = false;

            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    lcmVal = lcm(lcmVal, coins[i]);
                    if (lcmVal > x) {
                        tooBig = true;
                        break;
                    }
                }
            }

            if (tooBig) continue;

            long term = x / lcmVal;
            if (Integer.bitCount(mask) % 2 == 1) {
                count += term;
            } else {
                count -= term;
            }
        }

        return count;
    }

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

    private long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }
}

class Solution:
    def findKthSmallest(self, coins, k):
        min_coin = coins[0]

        for c in coins:
            min_coin = min(min_coin, c)

        lo = 1
        hi = k * min_coin

        while lo < hi:
            mid = lo + (hi - lo) // 2

            if self.countUpTo(mid, coins) >= k:
                hi = mid
            else:
                lo = mid + 1

        return lo

    def countUpTo(self, x, coins):
        n = len(coins)
        count = 0

        for mask in range(1, 1 << n):
            lcm_val = 1
            too_big = False

            for i in range(n):
                if mask & (1 << i):
                    lcm_val = self.lcm(lcm_val, coins[i])

                    if lcm_val > x:
                        too_big = True
                        break

            if too_big:
                continue

            term = x // lcm_val

            if mask.bit_count() % 2 == 1:
                count += term
            else:
                count -= term

        return count

    def gcd(self, a, b):
        while b:
            a, b = b, a % b

        return a

    def lcm(self, a, b):
        return a // self.gcd(a, b) * b

class Solution {
public:
    long long findKthSmallest(vector<int>& coins, long long k) {
        int minCoin = coins[0];

        for (int c : coins) {
            minCoin = min(minCoin, c);
        }

        long long lo = 1;
        long long hi = k * minCoin;

        while (lo < hi) {
            long long mid = lo + (hi - lo) / 2;

            if (countUpTo(mid, coins) >= k) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }

        return lo;
    }

private:
    long long countUpTo(long long x, vector<int>& coins) {
        int n = coins.size();
        long long count = 0;

        for (int mask = 1; mask < (1 << n); mask++) {
            long long lcmVal = 1;
            bool tooBig = false;

            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    lcmVal = lcm(lcmVal, (long long)coins[i]);

                    if (lcmVal > x) {
                        tooBig = true;
                        break;
                    }
                }
            }

            if (tooBig) {
                continue;
            }

            long long term = x / lcmVal;

            if (__builtin_popcount(mask) % 2 == 1) {
                count += term;
            } else {
                count -= term;
            }
        }

        return count;
    }

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

        return a;
    }

    long long lcm(long long a, long long b) {
        return a / gcd(a, b) * b;
    }
};

class Solution {
    findKthSmallest(coins, k) {
        let minCoin = coins[0];

        for (const c of coins) {
            minCoin = Math.min(minCoin, c);
        }

        let lo = 1;
        let hi = k * minCoin;

        while (lo < hi) {
            const mid = lo + Math.floor((hi - lo) / 2);

            if (this.countUpTo(mid, coins) >= k) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }

        return lo;
    }

    countUpTo(x, coins) {
        const n = coins.length;
        let count = 0;

        for (let mask = 1; mask < (1 << n); mask++) {
            let lcmVal = 1;
            let tooBig = false;
            let bits = 0;

            for (let i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    bits++;

                    lcmVal = this.lcm(lcmVal, coins[i]);

                    if (lcmVal > x) {
                        tooBig = true;
                        break;
                    }
                }
            }

            if (tooBig) {
                continue;
            }

            const term = Math.floor(x / lcmVal);

            if (bits % 2 === 1) {
                count += term;
            } else {
                count -= term;
            }
        }

        return count;
    }

    gcd(a, b) {
        while (b !== 0) {
            const t = b;
            b = a % b;
            a = t;
        }

        return a;
    }

    lcm(a, b) {
        return (a / this.gcd(a, b)) * b;
    }
}