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 <= 1000
1 <= arr[i] <= 3 * 104
arr[0] == 1
arr[i]
is a prime number fori > 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 &
Try With Live Editor
Input
Output
#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]]
Copy The Code &
Try With Live Editor
Input
Output