<p>You are given an integer array <code>coins</code> representing coins of different denominations and an integer <code>k</code>.</p>

<p>You have an infinite number of coins of each denomination. However, you are <strong>not allowed</strong> to combine coins of different denominations.</p>

<p>Return the <code>k<sup>th</sup></code> <strong>smallest</strong> amount that can be made using these coins.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block" style="
    border-color: var(--border-tertiary);
    border-left-width: 2px;
    color: var(--text-secondary);
    font-size: .875rem;
    margin-bottom: 1rem;
    margin-top: 1rem;
    overflow: visible;
    padding-left: 1rem;
">
<p><strong>Input:</strong> <span class="example-io" style="
    font-family: Menlo,sans-serif;
    font-size: 0.85rem;
">coins = [3,6,9], k = 3</span></p>

<p><strong>Output:</strong> <span class="example-io" style="
    font-family: Menlo,sans-serif;
    font-size: 0.85rem;
"> 9</span></p>

<p><strong>Explanation:</strong> The given coins can make the following amounts:<br />
Coin 3 produces multiples of 3: 3, 6, 9, 12, 15, etc.<br />
Coin 6 produces multiples of 6: 6, 12, 18, 24, etc.<br />
Coin 9 produces multiples of 9: 9, 18, 27, 36, etc.<br />
All of the coins combined produce: 3, 6, <u><strong>9</strong></u>, 12, 15, etc.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block" style="
    border-color: var(--border-tertiary);
    border-left-width: 2px;
    color: var(--text-secondary);
    font-size: .875rem;
    margin-bottom: 1rem;
    margin-top: 1rem;
    overflow: visible;
    padding-left: 1rem;
">
<p><strong>Input:</strong><span class="example-io" style="
    font-family: Menlo,sans-serif;
    font-size: 0.85rem;
"> coins = [5,2], k = 7</span></p>

<p><strong>Output:</strong><span class="example-io" style="
    font-family: Menlo,sans-serif;
    font-size: 0.85rem;
"> 12 </span></p>

<p><strong>Explanation:</strong> The given coins can make the following amounts:<br />
Coin 5 produces multiples of 5: 5, 10, 15, 20, etc.<br />
Coin 2 produces multiples of 2: 2, 4, 6, 8, 10, 12, etc.<br />
All of the coins combined produce: 2, 4, 5, 6, 8, 10, <u><strong>12</strong></u>, 14, 15, etc.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= coins.length &lt;= 15</code></li>
	<li><code>1 &lt;= coins[i] &lt;= 25</code></li>
	<li><code>1 &lt;= k &lt;= 2 * 10<sup>9</sup></code></li>
	<li><code>coins</code> contains pairwise distinct integers.</li>
</ul>

from math import gcd

class Solution:
    def findKthSmallest(self, coins, k):
        coins = list(set(coins))  # Ensure coins are unique
        n = len(coins)
        max_coin = max(coins)
        total_masks = 1 << n
        lcm_dict = {}

        # Precompute LCMs and accumulate signs for all non-empty subsets of coins
        from functools import lru_cache

        @lru_cache(None)
        def compute_lcm(a, b):
            return a * b // gcd(a, b)

        max_search_value = k * max_coin  # Upper bound for search space

        for mask in range(1, total_masks):
            lcm = 1
            bits = 0
            valid = True
            for i in range(n):
                if (mask >> i) & 1:
                    bits += 1
                    c = coins[i]
                    lcm = compute_lcm(lcm, c)
                    if lcm > max_search_value:
                        valid = False
                        break
            if valid:
                sign = 1 if bits % 2 == 1 else -1
                if lcm in lcm_dict:
                    lcm_dict[lcm] += sign
                else:
                    lcm_dict[lcm] = sign

        # Convert lcm_dict to a list of tuples
        lcm_sign_list = [(lcm, sign) for lcm, sign in lcm_dict.items()]

        # Function to compute the count of numbers ≤ x that are divisible by at least one coin
        def count(x):
            total = 0
            for lcm_val, sign in lcm_sign_list:
                if lcm_val > x:
                    continue  # Skip LCMs larger than x
                total += sign * (x // lcm_val)
            return total

        # Binary search to find the k-th smallest amount
        left = 1
        right = max_search_value
        while left < right:
            mid = (left + right) // 2
            c = count(mid)
            if c >= k:
                right = mid
            else:
                left = mid + 1
        return left

116