Kth Smallest Amount With Single Denomination Combination

• Preprocessing (Optional but Recommended): Filter the coins array to remove any coin c1 that is a multiple of another coin c2 in the array. This is because any amount that is a multiple of c1 is also a multiple of c2, so c1 is redundant.
• Initialization: Create a min-priority queue to store arrays of [amount, original_coin]. For each non-redundant coin, add [coin, coin] to the priority queue.
• Iteration: Maintain a count of unique amounts found and the value of the last unique amount processed (last_amount).
• Main Loop: Repeatedly extract the element with the smallest amount from the priority queue.
  • If the extracted current_amount is the same as last_amount, it's a duplicate (e.g., 6 from coin 2 and 6 from coin 3). We ignore it but still process its next multiple.
  • If current_amount is greater than last_amount, it's a new unique amount. Increment the count and update last_amount.
  • If count reaches k, we have found our answer.
  • Add the next multiple, [current_amount + original_coin, original_coin], back into the priority queue.

The core idea is to treat the multiples of each coin as a sorted stream of numbers. We want to find the k-th smallest element from the union of these streams. A min-heap is the perfect data structure for this 'merging' operation.

We initialize the heap with the first multiple of each coin (the coin values themselves). Then, we repeatedly extract the minimum element from the heap. This element is the next smallest amount in the combined sequence. To handle cases where the same amount can be generated by different coins (e.g., 12 is a multiple of 3, 6), we only increment our count for new, unique amounts. After processing an amount m generated by a coin c, we add the next multiple, m + c, into the heap. We continue this process until we have found k unique amounts.

1import java.util.*;2 3class Solution {4    public long kthSmallestAmount(int[] coins, int k) {5        // This approach is too slow for the given constraints but illustrates the idea.6        // It would work for smaller k.7        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));8        9        // Pre-filtering coins can be an optimization but doesn't change the main complexity issue with large k.10        // For simplicity, we'll use all coins.11        for (int coin : coins) {12            pq.offer(new long[]{coin, coin});13        }14 15        long lastAmount = -1;16        int count = 0;17 18        while (!pq.isEmpty()) {19            long[] current = pq.poll();20            long currentAmount = current[0];21            long originalCoin = current[1];22 23            if (currentAmount > lastAmount) {24                count++;25                lastAmount = currentAmount;26                if (count == k) {27                    return currentAmount;28                }29            }30            31            // Add the next multiple, checking for overflow32            if (Long.MAX_VALUE - originalCoin >= currentAmount) {33                 pq.offer(new long[]{currentAmount + originalCoin, originalCoin});34            }35        }36        37        return -1; // Should not be reached38    }39}

• Preprocessing: As an optimization, filter the coins array. A coin c1 is redundant if it's a multiple of another coin c2. Removing these can reduce n and speed up the PIE calculation.
• Binary Search Setup: Define a search range for the answer. A safe range is [1, k * min_coin], as the k-th amount cannot be larger than the k-th multiple of the smallest coin.
• Binary Search Loop:
  • Pick a mid value in the current search range.
  • Calculate count = countLe(mid), which is the number of unique amounts less than or equal to mid.
  • If count >= k, it means mid is a potential answer, and the actual answer could be mid or something smaller. So, we record mid and shrink the search space to the lower half: high = mid - 1.
  • If count < k, mid is too small. The answer must be larger. We search in the upper half: low = mid + 1.
• countLe(M) Function (PIE):
  • This function calculates |U S_i| where S_i are multiples of coins[i] up to M.
  • Iterate through all 2^n - 1 non-empty subsets of the (filtered) coins.
  • For each subset, calculate the Least Common Multiple (LCM) of its elements. Be careful to handle potential long overflows during LCM calculation. If the LCM exceeds M, its contribution is zero.
  • If the subset size is odd, add M / lcm to the total count.
  • If the subset size is even, subtract M / lcm from the total count.
• Return Value: The binary search terminates when low > high, and the last recorded potential answer is the k-th smallest amount.

The search space for the answer can be huge, but we can efficiently find the k-th amount by binary searching on the value of the amount itself. For any candidate amount M, we need to determine its rank, i.e., how many unique amounts are less than or equal to M. Let's call this function countLe(M).

If countLe(M) < k, M is too small, and we must search for a larger amount. If countLe(M) >= k, M could be our answer, or the answer could be even smaller. This is the standard binary search pattern for finding the minimum value that satisfies a condition.

The countLe(M) function is the heart of this solution. The total number of amounts less than or equal to M is the size of the union of the sets of multiples for each coin. This is calculated using the Principle of Inclusion-Exclusion.

countLe(M) = Σ floor(M/c_i) - Σ floor(M/lcm(c_i, c_j)) + Σ floor(M/lcm(c_i, c_j, c_k)) - ...

We can implement this by iterating through all 2^n - 1 non-empty subsets of the coins. For each subset, we compute the LCM of the coins within it and add or subtract M / LCM based on the subset's size.

1import java.util.*;2 3class Solution {4    public long kthSmallestAmount(int[] coins, int k) {5        int n = coins.length;6        List<Integer> uniqueCoins = new ArrayList<>();7        Arrays.sort(coins);8        for (int i = 0; i < n; i++) {9            boolean isRedundant = false;10            for (int j = 0; j < i; j++) {11                if (coins[i] % coins[j] == 0) {12                    isRedundant = true;13                    break;14                }15            }16            if (!isRedundant) {17                uniqueCoins.add(coins[i]);18            }19        }20 21        int[] filteredCoins = uniqueCoins.stream().mapToInt(i -> i).toArray();22        n = filteredCoins.length;23 24        long low = 1;25        long high = (long) k * filteredCoins[0]; 26        long ans = high;27 28        while (low <= high) {29            long mid = low + (high - low) / 2;30            if (countLe(mid, filteredCoins) >= k) {31                ans = mid;32                high = mid - 1;33            } else {34                low = mid + 1;35            }36        }37        return ans;38    }39 40    private long countLe(long m, int[] coins) {41        int n = coins.length;42        long count = 0;43        for (int i = 1; i < (1 << n); i++) {44            long currentLcm = 1;45            int subsetSize = 0;46            for (int j = 0; j < n; j++) {47                if ((i & (1 << j)) != 0) {48                    subsetSize++;49                    currentLcm = lcm(currentLcm, coins[j]);50                    if (currentLcm > m) { // Optimization51                        currentLcm = m + 1;52                        break;53                    }54                }55            }56 57            if (currentLcm <= m) {58                if (subsetSize % 2 == 1) {59                    count += m / currentLcm;60                } else {61                    count -= m / currentLcm;62                }63            }64        }65        return count;66    }67 68    private long gcd(long a, long b) {69        return b == 0 ? a : gcd(b, a % b);70    }71 72    private long lcm(long a, long b) {73        if (a == 0 || b == 0) return 0;74        // Check for overflow before multiplication75        if (a > Long.MAX_VALUE / b) return Long.MAX_VALUE;76        long res = a * b / gcd(a, b);77        return res;78    }79}