786. K-th Smallest Prime Fraction
Medium
You are given a sorted integer array arr containing 1 and prime numbers, where all the integers of arr are unique. You are also given an integer k.
For every i and j where 0 <= i < j < arr.length, we consider the fraction arr[i] / arr[j].
Return the kth smallest fraction considered. Return your answer as an array of integers of size 2, where answer[0] == arr[i] and answer[1] == arr[j].
Example 1:
- Input: arr = [1,2,3,5], k = 3
- Output: [2,5]
- Explanation: The fractions to be considered in sorted order are:\ 1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.\ The third fraction is 2/5.
Example 2:
- Input: arr = [1,7], k = 1
- Output: [1,7]
Constraints:
2 <= arr.length <= 10001 <= arr[i] <= 3 * 104arr[0] == 1-
arr[i]is a prime number fori > 0. - All the numbers of
arrare unique and sorted in strictly increasing order. 1 <= k <= arr.length * (arr.length - 1) / 2
Follow up: Can you solve the problem with better than O(n2) complexity?
Solution:
class Solution {
/**
* @param Integer[] $arr
* @param Integer $k
* @return Integer[]
*/
function kthSmallestPrimeFraction($arr, $k) {
$n = count($arr);
$l = 0.0;
$r = 1.0;
while ($l < $r) {
$m = ($l + $r) / 2.0;
$fractionsNoGreaterThanM = 0;
$p = 0;
$q = 1;
for ($i = 0, $j = 1; $i < $n; ++$i) {
while ($j < $n && $arr[$i] > $m * $arr[$j])
++$j;
if ($j == $n)
break;
$fractionsNoGreaterThanM += $n - $j;
if ($p * $arr[$j] < $q * $arr[$i]) {
$p = $arr[$i];
$q = $arr[$j];
}
}
if ($fractionsNoGreaterThanM == $k)
return [$p, $q];
if ($fractionsNoGreaterThanM > $k)
$r = $m;
else
$l = $m;
}
throw new Exception("Kth smallest prime fraction not found.");
}
}
Contact Links
Top comments (0)