diff options
-rw-r--r-- | kth_smallest_amount_single_denom.c | 52 | ||||
-rw-r--r-- | kth_smallest_amount_single_denom.py | 50 |
2 files changed, 102 insertions, 0 deletions
diff --git a/kth_smallest_amount_single_denom.c b/kth_smallest_amount_single_denom.c new file mode 100644 index 0000000..f0a0a57 --- /dev/null +++ b/kth_smallest_amount_single_denom.c @@ -0,0 +1,52 @@ +// 3116. Kth Smallest Amount With Single Denomination Combination +#include "leetcode.h" + +/* + * 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 k'th smallest amount that can be made using these + * coins. + */ + +int gcd(int a, int b) { return !b ? a : gcd(b, a % b); } + +int lcm(int a, int b) { return a / gcd(a, b) * b; } + +int cnt(int *coins, int coinsSize, int x) { + int sum = 0; + for (int mask = 1; mask < (1 << coinsSize); mask++) { + int bits = __builtin_popcountll(mask); + int least_common = 1; + for (int j = 0; j < coinsSize; j++) + if (mask & (1 << j)) + least_common = lcm(least_common, coins[j]); + if (bits & 1) + sum += x / least_common; + else + sum -= x / least_common; + } + return sum; +} + +int bin_search(int *coins, int coinsSize, int k) { + int left = 1, right = 25LL * 2e9; + while (left < right) { + int mid = left + (right - left) / 2; + if (cnt(coins, coinsSize, mid) < k) + left = mid + 1; + else + right = mid; + } + return left; +} + +long long findKthSmallest(int *coins, int coinsSize, int k) { + return bin_search(coins, coinsSize, k); +} + +int main() { + int c1[] = {3, 6, 9}, c2[] = {5, 2}; + printf("%lld\n", findKthSmallest(c1, ARRAY_SIZE(c1), 3)); // expect: 9 + printf("%lld\n", findKthSmallest(c2, ARRAY_SIZE(c2), 7)); // expect: 12 +} diff --git a/kth_smallest_amount_single_denom.py b/kth_smallest_amount_single_denom.py new file mode 100644 index 0000000..36f1e93 --- /dev/null +++ b/kth_smallest_amount_single_denom.py @@ -0,0 +1,50 @@ +# 3116. Kth Smallest Amount With Single Denomination Combination +from collections import defaultdict +from itertools import combinations +from math import lcm + +""" +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 k'th smallest amount that can be made using these +coins. +""" + + +class Solution(object): + def findKthSmallest(self, coins, k): + """ + :type coins: List[int] + :type k: int + :rtype: int + """ + n, dic = len(coins), defaultdict(list) + for i in range(1, n + 1): + for comb in combinations(coins, i): + dic[len(comb)].append(lcm(*comb)) + + def cnt(dic, target): + res = 0 + for i in range(1, n + 1): + for j in dic[i]: + res += target // j * pow(-1, i + 1) + return res + + start, end = min(coins), min(coins) * k + while start + 1 < end: + mid = (start + end) // 2 + if cnt(dic, mid) >= k: + end = mid + else: + start = mid + if cnt(dic, start) >= k: + return start + else: + return end + + +if __name__ == "__main__": + obj = Solution() + print(obj.findKthSmallest(coins=[3, 6, 9], k=3)) + print(obj.findKthSmallest(coins=[5, 2], k=7)) |