Problem statement

https://leetcode.com/problems/k-th-smallest-prime-fraction/

Solution

On of the ways to solve this problem is to use binary search: for given number D ask question: how many fraction there is, which are less than this number D. It can be solved again, using binary search in O(n log n) time, as it is shown in the code above.

Complexity

Final time complexity is O(n log n log T), where T is biggest number in our A. Space is O(n).

Code 1

class Solution:
    def kthSmallestPrimeFraction(self, A, K):
        beg, end = 0, 1
        while end - beg > 1e-10:
            mid = (beg + end)/2
            if sum(bisect.bisect(A, mid*a) for a in A) < K:
                beg = mid
            else:
                end = mid

        return min((abs(a*mid - round(a*mid)), round(a*mid), a)  for a in A)[1:]

Code 2

Second binary search can be replaced with two pointers approach, so overall complexity is O(n log T).

Complexity

Time complexity is O(n log T), space is O(n).

class Solution:
    def kthSmallestPrimeFraction(self, A, K):
        def count(m):
            j, cnt, n = len(A)-1, 0, len(A)
            for i in range(n):
                while j >= 0 and A[i] > m*A[n-1-j]: j-=1
                cnt += (j + 1)
            return cnt
        
        beg, end = 0, 1
        while end - beg > 1e-10:
            mid = (beg + end)/2
            if count(mid) < K:
                beg = mid
            else:
                end = mid

        return min((abs(a*mid - round(a*mid)), round(a*mid), a)  for a in A)[1:]

Remark

This problem actually is special case of Problem 0378 Kth Smallest Element in a Sorted Matrix and Problem 0373 Find K Pairs with Smallest Sums: there is O((n+k)*log n) heaps solution and even overkill solution with O(n) complexity.

One weakness in all method I have seen so far is that we are working with double numbers, so if two fractions a1/b1 and a2/b2 are very close, than solution will not work if constrains in our problem will be bigger. One solution I see is try to use modified binary search, where we have two fractions a1/b1 < a2/b2 and we choose middle fraction as (a1+a2)/(b1+b2)`.