1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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))
|