K-th Smallest Prime Fraction
Problem
Given a sorted list of distinct primes (and 1) and integer K, find the K-th smallest fraction p/q where p < q are entries in the list.
arr=[1,2,3,5], K=3[2,5]import heapq
def kthSmallestPrimeFraction(arr, K):
n = len(arr)
h = [(arr[0]/arr[j], 0, j) for j in range(1, n)]
heapq.heapify(h)
for _ in range(K-1):
_, i, j = heapq.heappop(h)
if i + 1 < j:
heapq.heappush(h, (arr[i+1]/arr[j], i+1, j))
_, i, j = h[0]
return [arr[i], arr[j]]function kthSmallestPrimeFraction(arr, K) {
const n = arr.length;
const h = [];
for (let j = 1; j < n; j++) h.push([arr[0]/arr[j], 0, j]);
const cmp = (a,b) => a[0]-b[0];
for (let k = 0; k < K-1; k++) {
h.sort(cmp);
const [_, i, j] = h.shift();
if (i+1 < j) h.push([arr[i+1]/arr[j], i+1, j]);
}
h.sort(cmp);
const [, i, j] = h[0];
return [arr[i], arr[j]];
}int[] kthSmallestPrimeFraction(int[] arr, int K) {
int n = arr.length;
PriorityQueue<double[]> pq = new PriorityQueue<>((a,b) -> Double.compare(a[0], b[0]));
for (int j = 1; j < n; j++) pq.offer(new double[]{(double)arr[0]/arr[j], 0, j});
for (int k = 0; k < K-1; k++) {
double[] cur = pq.poll();
int i = (int)cur[1], j = (int)cur[2];
if (i+1 < j) pq.offer(new double[]{(double)arr[i+1]/arr[j], i+1, j});
}
double[] top = pq.peek();
return new int[]{arr[(int)top[1]], arr[(int)top[2]]};
}vector<int> kthSmallestPrimeFraction(vector<int>& arr, int K) {
int n = arr.size();
using T = tuple<double,int,int>;
priority_queue<T, vector<T>, greater<>> pq;
for (int j = 1; j < n; j++) pq.push({(double)arr[0]/arr[j], 0, j});
for (int k = 0; k < K-1; k++) {
auto [_, i, j] = pq.top(); pq.pop();
if (i+1 < j) pq.push({(double)arr[i+1]/arr[j], i+1, j});
}
auto [_, i, j] = pq.top();
return {arr[i], arr[j]};
}Explanation
We need the K-th smallest fraction arr[i]/arr[j]. Listing every fraction and sorting works but is wasteful; instead we pull the fractions out in sorted order one at a time using a min-heap.
The key observation: fix a denominator arr[j]. For that column, the smallest fraction uses the smallest numerator, arr[0]/arr[j]. So we seed the heap with one entry per column: arr[0]/arr[j] for every j from 1 onward.
Each heap item stores the value plus its indices (i, j). We pop the smallest fraction and, if there is a larger numerator left in that same column (i+1 < j), we push arr[i+1]/arr[j]. This way the next candidate from a column only appears after the previous one is taken.
We repeat the pop-and-push K-1 times. After those removals, the fraction now sitting at the heap top is the K-th smallest, and we return its numerator and denominator.
Example: arr=[1,2,3,5], K=3. Heap starts with 1/2, 1/3, 1/5. Pop 1/5 (push 2/5), pop 1/3 (push 2/3). The heap top is now 2/5, the 3rd smallest, so the answer is [2,5].