786

786. K-th Smallest Prime Fraction (Hard)

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 for i > 0.
• All the numbers of arr are unique and sorted in strictly increasing order.
• 1 <= k <= arr.length * (arr.length - 1) / 2

Companies:
Robinhood

Related Topics:
Array, Binary Search, Heap (Priority Queue)

Similar Questions:

• Kth Smallest Element in a Sorted Matrix (Medium)
• Kth Smallest Number in Multiplication Table (Hard)
• Find K-th Smallest Pair Distance (Hard)

Solution 1. Heap

// OJ: https://leetcode.com/problems/k-th-smallest-prime-fraction/
// Author: github.com/lzl124631x
// 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[0]] / A[a[1]] > (double)A[b[0]] / A[b[1]]; };
        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] };
    }
};