786. K-th Smallest Prime Fraction

Problem Statement

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

Follow up: Can you solve the problem with better than O(n2) complexity?

Intuition

Simalar to above priblem just that for finding no of ele smaller 
We use two pointer

Refer in the video

Links

https://leetcode.com/problems/k-th-smallest-prime-fraction/description/

Video Links

https://www.youtube.com/watch?v=SmxdebjWvfs&ab_channel=AryanMittal

Approach 1:

C++

class Solution {
public:
    vector<int> find_ans(vector<int>& arr, double mid){
        vector<int> ct(3,0);
        int n = arr.size();
        double max_ratio = 0;
        int count = 0, i=0, j=1;

        while(i < n-1){
            while(j<n and arr[i] >= mid*arr[j]){
                j++;
            }

            count += n-j;
            if(j==n)
                break;
            double cur_ratio = (arr[i]*1.0)/arr[j];
            // Smaller fractions can come afterwards, So
            // We take only large fractions i and j
            if(cur_ratio > max_ratio){
                max_ratio = cur_ratio;
                ct[1] = i;  ct[2] = j;
            }
            i++;
        }
        ct[0] = count;

        return ct;
    }

    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
        double low = 0, high = 1.0;
        int ansi, ansj;

        while(low < high){
            double mid = low + (high - low)/2;
            vector<int> ct = find_ans(arr, mid);
            int count = ct[0];

            if(count == k){
                ansi = ct[1];   ansj = ct[2];
                break;
            }else if(count > k){
                high = mid;
            }else{
                low = mid;
            }
        }
        
        return {arr[ansi], arr[ansj]};
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems