Kth Smallest Amount With Single Denomination Combination solution and explanation

import heapq

def kth_smallest_amount(coins, k):
    min_heap = []
    for coin in coins:
        heapq.heappush(min_heap, (coin, coin))
    
    count = 0
    while count < k:
        smallest, base = heapq.heappop(min_heap)
        count += 1
        if count == k:
            return smallest
        heapq.heappush(min_heap, (smallest + base, base))

# Example usage:
coins = [3, 6, 9]
k = 3
print(kth_smallest_amount(coins, k))  # Output: 9

import java.util.PriorityQueue;

public class KthSmallestAmount {
    public static int kthSmallestAmount(int[] coins, int k) {
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        for (int coin : coins) {
            minHeap.offer(new int[]{coin, coin});
        }

        int count = 0;
        while (count < k) {
            int[] current = minHeap.poll();
            int smallest = current[0];
            int base = current[1];
            count++;
            if (count == k) {
                return smallest;
            }
            minHeap.offer(new int[]{smallest + base, base});
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] coins = {3, 6, 9};
        int k = 3;
        System.out.println(kthSmallestAmount(coins, k)); // Output: 9
    }
}

import math

def kth_smallest_amount_math(coins, k):
    def count_divisible_by(coin, x):
        return x // coin

    low, high = 1, max(coins) * k
    while low < high:
        mid = (low + high) // 2
        if sum(count_divisible_by(coin, mid) for coin in coins) < k:
            low = mid + 1
        else:
            high = mid
    return low

# Example usage:
coins = [5, 2]
k = 7
print(kth_smallest_amount_math(coins, k))  # Output: 12

public class KthSmallestAmountMath {
    public static int kthSmallestAmount(int[] coins, int k) {
        int low = 1, high = coins[0] * k;
        for (int coin : coins) {
            high = Math.max(high, coin * k);
        }

        while (low < high) {
            int mid = (low + high) / 2;
            int count = 0;
            for (int coin : coins) {
                count += mid / coin;
            }
            if (count < k) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        int[] coins = {5, 2};
        int k = 7;
        System.out.println(kthSmallestAmount(coins, k)); // Output: 12
    }
}

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;
    }
};

function findKthSmallest(coins: number[], k: number): number {
    let [l, r] = [1n, BigInt(1e11)];
    const n = coins.length;
    const check = (mx: bigint): boolean => {
        let cnt = 0n;
        for (let i = 1; i < 1 << n; ++i) {
            let v = 1n;
            for (let j = 0; j < n; ++j) {
                if ((i >> j) & 1) {
                    v = lcm(v, BigInt(coins[j]));
                    if (v > mx) {
                        break;
                    }
                }
            }
            const m = bitCount(i);
            if (m & 1) {
                cnt += mx / v;
            } else {
                cnt -= mx / v;
            }
        }
        return cnt >= BigInt(k);
    };
    while (l < r) {
        const mid = (l + r) >> 1n;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1n;
        }
    }
    return Number(l);
}

function gcd(a: bigint, b: bigint): bigint {
    return b === 0n ? a : gcd(b, a % b);
}

function lcm(a: bigint, b: bigint): bigint {
    return (a * b) / gcd(a, b);
}

function bitCount(i: number): number {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

func findKthSmallest(coins []int, k int) int64 {
	var r int = 1e11
	n := len(coins)
	ans := sort.Search(r, func(mx int) bool {
		cnt := 0
		for i := 1; i < 1<<n; i++ {
			v := 1
			for j, x := range coins {
				if i>>j&1 == 1 {
					v = lcm(v, x)
					if v > mx {
						break
					}
				}
			}
			m := bits.OnesCount(uint(i))
			if m%2 == 1 {
				cnt += mx / v
			} else {
				cnt -= mx / v
			}
		}
		return cnt >= k
	})
	return int64(ans)
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func lcm(a, b int) int {
	return a * b / gcd(a, b)
}