<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:
    # Inclusion-Exclusion Principle Using LCM: 
    #  Count multiples of 2: Let this be M2.
    #  Count multiples of 3: Let this be M3.
    #  Subtract the count of common multiples of 2 and 3 (i.e., multiples of LCM(2, 3)): Let this be M6.
    #  The correct count of numbers that are divisible by either 2 or 3 up to X is:  Count = M2 + M3 - M6
    def findKthSmallest(self, coins: List[int], k: int) -> int:
        if 1 in coins:  # optimization 
            return k
        # another optimization to reduce the coins list size
        dedup_coins = []
        for coin in coins:
            for new_coin in dedup_coins:
                if coin % new_coin == 0:
                    break
            else: 
                dedup_coins.append(coin)

        if len(dedup_coins) == 1: # another optimization
            return dedup_coins[0] * k

        coins = dedup_coins

        n = len(coins)
        # map from each power-set's size to its LCMs, the power-set's size is used for the Inclusion-Exclusion Principle. 
        lcm_dict = defaultdict(list)
        for i in range(1, n + 1):
            for comb in itertools.combinations(coins, i):
                # assert i == len(comb)
                lcm_dict[i].append(math.lcm(*comb))
        
        # Binary Search on result.
        def count_no_bigger(target_number):
            # Inclusion-Exclusion Principle using LCM 
            res = 0
            for set_size, lcm_list in lcm_dict.items():
                for lcm in lcm_list:
                    # Note Python uses floor division: 
                    # (10 // 3) * -1 => -3
                    # 10 // (3 * -1) => -4
                    coefficient = pow(-1, set_size + 1)
                    res += (target_number // lcm) * coefficient
            return res
        

        l, r = min(coins), min(coins) * k + 1
        while l  < r:
            mid = l + (r - l) // 2
            if count_no_bigger(mid) >= k:
                r = mid
            else:
                l = mid + 1
        return l
66