3116. Kth Smallest Amount With Single Denomination Combination LeetCode Solution
In this guide, you will get 3116. Kth Smallest Amount With Single Denomination Combination LeetCode Solution with the best time and space complexity. The solution to Kth Smallest Amount With Single Denomination Combination problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Kth Smallest Amount With Single Denomination Combination
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.
Time Complexity: O(2^{|\texttt{coins}|} \cdot \log k)
Space Complexity: O(2^{|\texttt{coins}|})
3116. Kth Smallest Amount With Single Denomination Combination LeetCode Solution in C++
class Solution {
public:
long long findKthSmallest(vector<int>& coins, int k) {
const vector<vector<long>> sizeToLcms = getSizeToLcms(coins);
long l = 0;
long r = static_cast<long>(k) * ranges::min(coins);
while (l < r) {
const long m = (l + r) / 2;
if (numDenominationsNoGreaterThan(sizeToLcms, m) >= k)
r = m;
else
l = m + 1;
}
return l;
}
private:
// Returns the number of denominations <= m.
long numDenominationsNoGreaterThan(const vector<vector<long>>& sizeToLcms,
long m) {
long res = 0;
for (int sz = 1; sz < sizeToLcms.size(); ++sz)
for (const long lcm : sizeToLcms[sz])
// Principle of Inclusion-Exclusion (PIE)
res += m / lcm * pow(-1, sz + 1);
return res;
};
// Returns the LCMs for each number of combination of coins.
vector<vector<long>> getSizeToLcms(const vector<int>& coins) {
const int n = coins.size();
const int maxMask = 1 << n;
vector<vector<long>> sizeToLcms(n + 1);
for (unsigned mask = 1; mask < maxMask; ++mask) {
long lcmOfSelectedCoins = 1;
for (int i = 0; i < n; ++i)
if (mask >> i & 1)
lcmOfSelectedCoins = lcm(lcmOfSelectedCoins, coins[i]);
sizeToLcms[popcount(mask)].push_back(lcmOfSelectedCoins);
}
return sizeToLcms;
}
}; /* code provided by PROGIEZ */
3116. Kth Smallest Amount With Single Denomination Combination LeetCode Solution in Java
class Solution {
public long findKthSmallest(int[] coins, int k) {
List<Long>[] sizeToLcms = getSizeToLcms(coins);
long l = 0;
long r = (long) k * Arrays.stream(coins).min().getAsInt();
while (l < r) {
final long m = (l + r) / 2;
if (numDenominationsNoGreaterThan(sizeToLcms, m) >= k)
r = m;
else
l = m + 1;
}
return l;
}
// Returns the number of denominations <= m.
private long numDenominationsNoGreaterThan(List<Long>[] sizeToLcms, long m) {
long res = 0;
for (int sz = 1; sz < sizeToLcms.length; ++sz)
for (long lcm : sizeToLcms[sz])
res += m / lcm * Math.pow(-1, sz + 1);
return res;
}
// Returns the LCMs for each number of combination of coins.
private List<Long>[] getSizeToLcms(int[] coins) {
final int n = coins.length;
final int maxMask = 1 << n;
List<Long>[] sizeToLcms = new List[n + 1];
for (int i = 1; i <= n; ++i)
sizeToLcms[i] = new ArrayList<>();
for (int mask = 1; mask < maxMask; ++mask) {
long lcmOfSelectedCoins = 1;
for (int i = 0; i < n; ++i)
if ((mask >> i & 1) == 1)
lcmOfSelectedCoins = lcm(lcmOfSelectedCoins, coins[i]);
sizeToLcms[Integer.bitCount(mask)].add(lcmOfSelectedCoins);
}
return sizeToLcms;
}
private long lcm(long a, long b) {
return a * b / gcd(a, b);
}
private long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
} // code provided by PROGIEZ
3116. Kth Smallest Amount With Single Denomination Combination LeetCode Solution in Python
class Solution:
def findKthSmallest(self, coins: list[int], k: int) -> int:
sizeToLcms = self._getSizeToLcms(coins)
def count(m: int) -> int:
"""Returns the number of denominations <= m."""
res = 0
for sz, lcms in enumerate(sizeToLcms):
for lcm in lcms:
# Principle of Inclusion-Exclusion (PIE)
res += m // lcm * pow(-1, sz + 1)
return res
return bisect.bisect_left(range(k * min(coins)), k, key=count)
def _getSizeToLcms(self, coins: list[int]) -> list[list[int]]:
# Returns the LCMs for each number of combination of coins.
sizeToLcms = [[] for _ in range(len(coins) + 1)]
for sz in range(1, len(coins) + 1):
for combination in itertools.combinations(coins, sz):
sizeToLcms[sz].append(math.lcm(*combination))
return sizeToLcms # code by PROGIEZ
