## Algorithm

Problem Name: 786. K-th Smallest Prime Fraction

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 == arr[i]` and `answer == 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 == 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`

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const kthSmallestPrimeFraction = function(A, K) {
let ans = []
let left = 0.0
let right = 1.0
while (right - left > 1e-9) {
const mid = left + (right - left) / 2
const { count, p, q } = maxUnder(mid, A)
if (count >= K) {
ans = [p, q]
right = mid
} else {
left = mid
}
}
return ans

function maxUnder(x, primes) {
let [p, q] = [0, 1]
let count = 0
let l = -1
for (let r = 1; r < primes.length; r++) {
while (primes[l + 1] < primes[r] * x) {
l += 1
}
count += l + 1
if (l >= 0 && p * primes[r] < q * primes[l]) {
;[p, q] = [primes[l], primes[r]]
}
}
return { count, p, q }
}
}
``````
Copy The Code &

Input

cmd
arr = [1,2,3,5], k = 3

Output

cmd
[2,5]

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def kthSmallestPrimeFraction(self, A, K):
heap, used = [(A / A[-1], 0, len(A) - 1)], {(0, len(A) - 1)}
for i in range(K):
try:
cur, l, r = heapq.heappop(heap)
if (l + 1, r) not in used:
heapq.heappush(heap, (A[l + 1] / A[r], l + 1, r))
if (l, r - 1) not in used:
heapq.heappush(heap, (A[l] / A[r - 1], l, r - 1))
except:
break
return [A[l], A[r]]
``````
Copy The Code &

Input

cmd
arr = [1,2,3,5], k = 3

Output

cmd
[2,5]