aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--kth_smallest_amount_single_denom.c52
-rw-r--r--kth_smallest_amount_single_denom.py50
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))