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

def find_lcm(a, b):
    return abs(a * b) // gcd(a, b)


def calc_lcm(*nums):
    return reduce(find_lcm, nums)


def get_all_comb(coins):
    combs = chain.from_iterable(
        combinations(coins, i) for i in range(1, len(coins) + 1)
    )
    return list(combs)


def inclusion_exclusion(kit):
    has_odd_length = len(kit) & 1
    return 1 if has_odd_length else -1


def find_pos_insequence(val, kits):
    """find position of {val} in sequence generated by {kits} s.t.
    return value
     - will denotes the position of [val] if [val] is valid number of sequence
     - will denotes the position of valid value on left to [val] of sequence
    """
    cardinality = 0  # total elements behind in sequenece
    for kit in kits:
        start = calc_lcm(*kit)
        # position of [val] in sequence generated by [start] S.T. (start * i) <= val
        # {pos} will be leftmost position of valid candidate to [val] if [val] is not valid candidate
        pos = val // start
        cardinality += inclusion_exclusion(kit) * pos
    return cardinality


class Solution:
    def findKthSmallest(self, coins: List[int], k: int) -> int:
        upper_k = 2 * 10**9
        all_combs = get_all_comb(coins)

        l = 1  # first value in sequence
        # eqn = a + (n-1) * d
        r = 25 + ((upper_k - 1) * 25)  # possible last value in sequence (in worst case)

        res = 1
        while l <= r:
            amt = (l + r) // 2
            pos = find_pos_insequence(amt, all_combs)

            if pos < k:
                l = amt + 1
            else:
                # look for more smaller value because its not ensured that [amt] is actually part of a sequence
                r = amt - 1
                res = amt

        return res
966