K Th Smallest Prime Fraction - Leetcode Solution

The problem of Kth smallest prime fraction on Leetcode is a popular algorithmic problem. The problem statement is as follows:

You are given a sorted integer array A and two integers K and N. Find the K-th smallest fraction of the possible fractions generated by choosing two different numbers from the array.

The problem is to find the Kth smallest fraction in the list of all possible fractions formed by choosing any two numbers from the given array. The fractions must be in the ascending order of their values.

Approach:

One way to solve this problem is using binary search. We can start by assuming the range of our answer to be between 0 and 1. We can then use binary search to narrow down our range to a fraction that contains exactly K fractions. We can achieve this by assuming the mid point of our range as a candidate for the required answer and counting how many fractions in the array A are less than or equal to this fraction. If there are less than K such fractions, we move the left boundary to mid, else we move the right boundary to mid. We repeat this process until we arrive at the solution.

We can further optimize the binary search by using two pointers. We can assume the second pointer (j) starts at the end of the array, and while traversing the array, we can skip over any values for which i<j and A[i]/A[j] is less than our current candidate. This is because for any value i<j, the value A[i]/A[j] will only decrease as j moves towards i, and hence any value less than our current candidate can be ignored.

Detailed algorithm:

1. Set the low and high boundaries of the range as 0 and 1 respectively.
2. While the low boundary is less than the high boundary: a. Set the mid point as the average of low and high. b. Set the counters count and num as 0. c. Start a loop with two pointers i and j, with i as the first value and j as the last value in the array. Traverse the array: i. Increment the counter count if A[i]/A[j] is less than or equal to mid. ii. Move the pointer i to the right if A[i]/A[j] is less than or equal to mid. iii. Move the pointer j to the left, else continue to next value of i. d. Check if count is less than K. If so, move the low boundary to mid. Else, move the high boundary to mid.

Code:

1