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

class Solution:
    def findKthSmallest(self, coins: List[int], k: int) -> int:
        return sol2(coins, k)

def sol1(nums, k):
    N = len(nums)

    def get_count(target):
        dp = [0] * (target//2)
        for num in nums:
            acc = num
            while acc * acc < target:
                dp[acc] = 1
                acc += num
        ans = 0
        for i in range(0, target//2):
            if dp[i] != 0:
                ans += 1
        return ans

    ans = -1
    lo = 0
    hi = max(nums) * k
    while lo <= hi:
        mi = lo + (hi - lo) // 2
        if get_count(mi) < k:
            ans = mi
            lo = mi + 1
        else:
            hi = mi - 1
    return ans

# x 2x 3 x 4x ... Nx
# Nx < target
# N < target // x

# 1  2  3  4  5  6  7  8  9 10
# 2  4  6  8 10 12 14 16 18 20
# 3  6  9 12 15 18 21 24 27 30
# 5 10 15 20 25 30 35 40 45 50

def sol2(nums: list[int], k: int) -> int:
    N = len(nums)

    def is_good(target: int) -> bool:
        total = 0
        for i in range(1, 1 << N):
            L = 1
            cnt = 0
            for j in range(N):
                if i & (1 << j) != 0:
                    L = lcm(L, nums[j])
                    cnt += 1
            if cnt % 2 != 0:
                total += target // L
            else:
                total -= target // L
        return total >= k

    lo = 0
    hi = 25 * 2 * 10**9 + 1
    ans = -1
    while lo <= hi:
        mi = lo + (hi - lo) // 2
        if is_good(mi):
            ans = mi
            hi = mi - 1
        else:
            lo = mi + 1
    return ans

1366