3116. Kth Smallest Amount With Single Denomination Combination

Description

You are given an integer array coins representing coins of different denominations and an integer k.

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

Return the kth smallest amount that can be made using these coins.

 

Example 1:

Input: coins = [3,6,9], k = 3

Output: 9

Explanation: The given coins can make the following amounts:
Coin 3 produces multiples of 3: 3, 6, 9, 12, 15, etc.
Coin 6 produces multiples of 6: 6, 12, 18, 24, etc.
Coin 9 produces multiples of 9: 9, 18, 27, 36, etc.
All of the coins combined produce: 3, 6, 9, 12, 15, etc.

Example 2:

Input: coins = [5,2], k = 7

Output: 12

Explanation: The given coins can make the following amounts:
Coin 5 produces multiples of 5: 5, 10, 15, 20, etc.
Coin 2 produces multiples of 2: 2, 4, 6, 8, 10, 12, etc.
All of the coins combined produce: 2, 4, 5, 6, 8, 10, 12, 14, 15, etc.

 

Constraints:

• 1 <= coins.length <= 15
• 1 <= coins[i] <= 25
• 1 <= k <= 2 * 109
• coins contains pairwise distinct integers.

 

Solutions

Solution: Stack

• Time complexity: O(2ⁿ*n+2ⁿlog(k*Min(coins)))
• Space complexity: O(2ⁿ)

 

JavaScript

/**
 * @param {number[]} coins
 * @param {number} k
 * @return {number}
 */
const findKthSmallest = function (coins, k) {
  const n = coins.length;
  const maxMask = (1 << n) - 1;
  const lcmsPerPickSize = Array.from({ length: n + 1 }, () => []);
  let left = 1;
  let right = Math.min(...coins) * k;

  const isSmallerThanK = denomination => {
    let count = 0;

    for (let size = 1; size <= n; size++) {
      const sign = size % 2 ? 1 : -1;

      for (const value of lcmsPerPickSize[size]) {
        // 排容原理（PIE）
        count += Math.floor(denomination / value) * sign;
      }
    }

    return count < k;
  };

  for (let mask = 1; mask <= maxMask; mask++) {
    let currentLcm = 1;

    for (let index = 0; index < n; index++) {
      const isUsed = Boolean((mask >> index) & 1);

      if (!isUsed) continue;

      currentLcm = lcm(currentLcm, coins[index]);
    }

    const pickSize = popcount(mask);

    lcmsPerPickSize[pickSize].push(currentLcm);
  }

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    isSmallerThanK(mid) ? (left = mid + 1) : (right = mid - 1);
  }

  return left;
};

function gcd(a, b) {
  return b ? gcd(b, a % b) : a;
}

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

function popcount(x) {
  let count = 0;

  while (x) {
    x &= x - 1;
    count += 1;
  }

  return count;
}