aboutsummaryrefslogtreecommitdiff
path: root/kth_smallest_amount_single_denom.py
diff options
context:
space:
mode:
Diffstat (limited to 'kth_smallest_amount_single_denom.py')
-rw-r--r--kth_smallest_amount_single_denom.py50
1 files changed, 50 insertions, 0 deletions
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))