Problem Explanation

Given a sorted list containing 1 and some prime numbers, we are to determine the k-th smallest fraction that can be obtained from combinations of the numbers in the array. As long as one number (p) is smaller than the other (q), we can consider the fraction p/q.

We solve this problem through binary search between high value (1.0) and low value (0.0). Our aim is to calculate the middle value and determine whether the number of fractions less than or equal to this middle value is greater than, less than, or equal to k.

If the number of fractions is greater than k, we adjust our boundary by setting the high value as the mid value. However, if it is less than k, we adjust our boundary by setting the low value as the mid value. If it is equal to k, we return the fraction (p, q) such that p/q <= mid-value.

Walkthrough

Consider the array A = [1, 2, 3, 5], K = 3. Here are the fractions that can be formed:

1/2, 1/3, 1/5, 2/3, 2/5, 3/5

Sorting these yields:

1/5, 1/3, 2/5, 1/2, 2/3, 3/5

The third smallest fraction is 2/5, thus our output is [2, 5].

Now, let's look at the solution code in different languages.

Python Solution

1
2python
3class Solution:
4    def kthSmallestPrimeFraction(self, arr: List[int], K: int) -> List[int]:
5        low, high = 0.0, 1.0  # initial boundaries
6        while high - low > 1e-9:
7            mid = low + (high - low) / 2.0
8            fractionsNoGreaterThanM, maxFraction, i = 0, (0, 1), 0
9            # iterate through array elements
10            for idx in range(1, len(arr)):
11                while arr[i] < mid * arr[idx]: i += 1
12                fractionsNoGreaterThanM += i
13                if i > 0 and maxFraction[0] / maxFraction[1] < arr[i - 1] / arr[idx]:
14                    maxFraction = (arr[i - 1], arr[idx])
15                    
16            # check if number of fractions no greater than mid is less than, greater than, or equal to K
17            if fractionsNoGreaterThanM == K: return maxFraction
18            elif fractionsNoGreaterThanM < K: low = mid
19            else: high = mid
20        return []

Java Solution

1
2java
3import java.util.*;
4public class Solution {
5    public int[] kthSmallestPrimeFraction(int[] A, int K) {
6        double l = 0, r = 1;
7        double mid = 0;
8        int[] ans = new int[2];
9        
10        while (r-l>1e-9) {
11            mid = l + (r-l)/2;
12            int j=0,counter=0;
13            double max=0;
14            
15            for (int i=1; i<A.length; ++i) {
16                while (j<i && A[j]<=mid*A[i]) j++;
17                counter += j;
18                
19                if (j>0 && max<A[j-1]*1.0/A[i]) {
20                    max = A[j-1]*1.0/A[i];
21                    ans[0] = A[j-1];
22                    ans[1] = A[i];
23                }
24            }
25            
26            if (counter==K) return ans;
27            if (counter<K) l = mid;
28            else r = mid;
29        }
30        
31        return ans;
32    }
33}

Javascript Solution

1
2javascript
3var kthSmallestPrimeFraction = function(A, K) {
4    let lo = 0, hi = 1, mid;
5    let p = 0, q = 1;
6    while (hi - lo > 1e-9) {
7        mid = (lo + hi) / 2.0;
8        let total = 0;
9        for (let i = 0, j = 1; i < A.length - 1; i++) {
10            while (j < A.length && A[i] > A[j] * mid) j++;
11            if (j === A.length) break;
12            total += A.length - j;
13            if (A[j] * p > q * A[i]) {
14                p = A[i];
15                q = A[j];
16            }
17        }
18        if (total === K) return [p, q];
19        else if (total > K) hi = mid;
20        else lo = mid;
21    }
22};

C++ Solution

1
2cpp
3class Solution {
4public:
5    vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
6        int n = A.size();
7        double l = 0, r = 1;
8        while (l < r) {
9            double m = (l + r) / 2;
10            int total = 0;
11            int p = 0, q = 1;
12            for (int i = 0, j = 1; i < n - 1; ++i) {
13                while (j < n && A[i] > m * A[j]) ++j;
14                if (j == n) break;
15                total += n - j;
16                if (A[j] * p > q * A[i]) {
17                    p = A[i];
18                    q = A[j];
19                }
20            }
21            if (total == K) return {p, q};
22            else if (total > K) r = m;
23            else l = m;
24        }
25        return {};
26    }
27};

C# Solution

1
2csharp
3public class Solution 
4{
5    public int[] KthSmallestPrimeFraction(int[] A, int K) 
6    {
7        double l = 0, r = 1;
8        double m = 0;
9        int[] ans = new int[2];
10
11        while (r - l > 1e-9) 
12        {
13            m = l + (r - l) / 2;
14            int j = 0, count = 0;
15            int max = 0;
16
17            for (int i = 1; i < A.Length; ++i) 
18            {
19                while (j < i && A[j] <= m * A[i]) j++;
20                count += j;
21
22                if (j > 0 && max < A[j-1] / A[i]) 
23                {
24                    max = A[j - 1] / A[i];
25                    ans[0] = A[j - 1];
26                    ans[1] = A[i];
27                }
28            }
29            if (count == K) return ans;
30            if (count < K) l = m;
31            else r = m;
32        }
33
34        return ans;
35    }
36}

Ruby Solution

1
2ruby
3class Solution
4    def kth_smallest_prime_fraction(a, k)
5        low, high = [0.0, 1.0]
6        while high - low > 1e-9
7            mid = low + (high-low) / 2.0
8            fractions_no_greater_than_m, max_fraction, i = 0, [0, 1], 0
9            a.each_with_index do |num, idx|
10                next if idx.zero?
11                i += 1 while a[i] < mid * num
12                fractions_no_greater_than_m += i
13                if i > 0 && num * max_fraction[1] > max_fraction[0] * a[idx]
14                    max_fraction = [a[i-1], num]
15                end
16            end
17            if fractions_no_greater_than_m > k
18                high = mid
19            elsif fractions_no_greater_than_m < k
20                low = mid
21            else
22                return max_fraction
23            end
24        end
25        []
26    end
27end

The Ruby solution uses iterative methods to traverse through the elements of the array. It keeps track of the number of fractions no greater than the current mid-value, and the maximum fraction (p, q) where p/q <= mid. Based on these, it adjusts the boundaries of the binary search process.

End Notes

This problem sheds light on how complex problems can be solved using the binary search algorithm. As evident from the solutions, the algorithm can be implemented quite effectively using different programming languages. It is essential to understand and grasp the concept of binary search as it forms the basis for solving many other complex calculation and search problems in real-world applications.