Leetcode 786. K-th Smallest Prime Fraction
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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.