aboutsummaryrefslogtreecommitdiff
path: root/kth_smallest_prime_fraction.py
blob: a64d1d1155a027044ce0446322e8a77015c01891 (plain)
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
# 786. K-th Smallest Prime Fraction
from bisect import bisect

"""
given a sorted integer array 'arr' containing '1' and  prime numbers where
all the integers of 'arr' are unique. you are also given an integer 'k'. for
every 'i' and 'j' where '0 <= i < j < arr.len', we consider the fraction
'arr[i] / arr[j]'. return the k'th smallest fraction considered. return your
answer as an array of integers of size '2'.
"""


class Solution(object):
    def kthSmallestPrimeFraction(self, arr, k):
        """
        :type arr: List[int]
        :type k: int
        :rtype: List[int]
        """
        left, right, n = 0, 1, len(arr)
        while True:
            mid = (left + right) / 2
            border = [bisect(arr, arr[i] / mid) for i in range(n)]
            curr = sum(n - i for i in border)
            if curr > k:
                right = mid
            elif curr < k:
                left = mid
            else:
                return max(
                    [(arr[i], arr[j]) for i, j in enumerate(border) if j < n],
                    key=lambda x: x[0] / x[1],
                )


if __name__ == "__main__":
    obj = Solution()
    print(obj.kthSmallestPrimeFraction(arr=[1, 2, 3, 5], k=3))
    print(obj.kthSmallestPrimeFraction(arr=[1, 7], k=1))