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[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] == 1arr[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
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 }
}
}
Input
arr = [1,2,3,5], k = 3
Output
[2,5]
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def kthSmallestPrimeFraction(self, A, K):
heap, used = [(A[0] / A[-1], 0, len(A) - 1)], {(0, len(A) - 1)}
for i in range(K):
try:
cur, l, r = heapq.heappop(heap)
used.add((l, r))
if (l + 1, r) not in used:
heapq.heappush(heap, (A[l + 1] / A[r], l + 1, r))
used.add((l + 1, r))
if (l, r - 1) not in used:
heapq.heappush(heap, (A[l] / A[r - 1], l, r - 1))
used.add((l, r - 1))
except:
break
return [A[l], A[r]]
Input
arr = [1,2,3,5], k = 3
Output
[2,5]