diff options
Diffstat (limited to 'kth_smallest_prime_fraction.py')
-rw-r--r-- | kth_smallest_prime_fraction.py | 39 |
1 files changed, 39 insertions, 0 deletions
diff --git a/kth_smallest_prime_fraction.py b/kth_smallest_prime_fraction.py new file mode 100644 index 0000000..a64d1d1 --- /dev/null +++ b/kth_smallest_prime_fraction.py @@ -0,0 +1,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)) |