## DEV Community

MD ARIFUL HAQUE

Posted on • Updated on

# 786. K-th Smallest Prime Fraction

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 <= 1000`
• `1 <= arr[i] <= 3 * 104`
• `arr[0] == 1`
• `arr[i]` is a prime number for `i > 0`.
• All the numbers of `arr` are 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;
}