Formatted question description: https://leetcode.ca/all/786.html

# 786. K-th Smallest Prime Fraction

Hard

## Description

A sorted list A contains 1, plus some number of primes. Then, for every p < q in the list, we consider the fraction p/q.

What is the K-th smallest fraction considered? Return your answer as an array of ints, where answer = p and answer = q.

Examples:

Input: A = [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, 2/3. The third fraction is 2/5.

Input: A = [1, 7], K = 1

Output: [1, 7]

Note:

• A will have length between 2 and 2000.
• Each A[i] will be between 1 and 30000.
• K will be between 1 and A.length * (A.length - 1) / 2.

## Solution

Use a priority queue to store the fractions, where the smallest fraction is polled first. Initially, offer all [A, A[i]] where 0 < i < A.length to the priority queue. Since A is 1 and the smallest fraction has a numerator 1, the smallest fraction is in the priority queue.

Then poll the smallest fraction from the priority queue for K - 1 times. To ensure that the remaining smallest fraction is in the priority queue, each time a fraction is polled, try to find the next smallest fraction and offer it to the priority queue if it exists. Suppose the fraction polled is [A[i], A[j]] where 0 <= i < j < A.length. If i + 1 < j, then offer the new fraction [A[i + 1], A[j]] to the priority queue.

After the K - 1 times, the next element to be polled from the priority queue is the K-th smallest prime fraction, so return the fraction.

• class Solution {
public int[] kthSmallestPrimeFraction(int[] A, int K) {
Map<Integer, Integer> numIndexMap = new HashMap<Integer, Integer>();
int length = A.length;
for (int i = 0; i < length; i++)
numIndexMap.put(A[i], i);
PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] fraction1, int[] fraction2) {
return fraction1 * fraction2 - fraction2 * fraction1;
}
});
for (int i = 1; i < length; i++) {
int[] fraction = {A, A[i]};
}
for (int i = 1; i < K; i++) {
int[] fraction = priorityQueue.poll();
int numeratorIndex = numIndexMap.get(fraction), denominatorIndex = numIndexMap.get(fraction);
if (numeratorIndex + 1 < denominatorIndex) {
numeratorIndex++;
int[] newFraction = {A[numeratorIndex], fraction};
priorityQueue.offer(newFraction);
}
}
return priorityQueue.peek();
}
}

• // OJ: https://leetcode.com/problems/k-th-smallest-prime-fraction/
// Time: O(KlogN)
// Space: O(N)
class Solution {
typedef array<int, 2> T;
public:
vector<int> kthSmallestPrimeFraction(vector<int>& A, int k) {
auto cmp = [&](T &a, T &b) { return (double)A[a] / A[a] > (double)A[b] / A[b]; };
priority_queue<T, vector<T>, decltype(cmp)> pq(cmp);
for (int i = 0; i < A.size() - 1; ++i) pq.push({ i, (int)A.size() - 1 });
while (--k) {
auto [a, b]  = pq.top();
pq.pop();
if (a != b - 1) pq.push({ a, b - 1 });
}
auto [a, b] = pq.top();
return { A[a], A[b] };
}
};

• print("Todo!")