Question

Code

class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:

        l, r = 0, 1
        A = len(arr)
        p = q = 0

		# Time complexity: n * log(10 ^ 9)
    
        while l < r:
            m = (l + r) / 2
            j = 1
            cnt = 0
            max_frac = 0

			# For each i, find number of elem smaller than m
			# j can remain at the same position, since the array is in increasing order
            for i in range(A - 1):
                
                while j < A and arr[i]/arr[j] > m:
                    j += 1
                    
                if j == A:
                    break

                cnt += A - j
                
                if arr[i]/arr[j] > max_frac:
                    p, q = arr[i], arr[j]
                    max_frac = p/q

            

            if cnt == k:
                return p, q
            elif cnt < k:
                l = m
            else:
                r = m