> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/binary-search/bs-over-answer-space-answer-space/786.-k-th-smallest-prime-fraction.md).

# 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]`.

&#x20;

**Example 1:**

<pre><code><strong>Input: arr = [1,2,3,5], k = 3
</strong><strong>Output: [2,5]
</strong><strong>Explanation: The fractions to be considered in sorted order are:
</strong>1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.
The third fraction is 2/5.
</code></pre>

**Example 2:**

<pre><code><strong>Input: arr = [1,7], k = 1
</strong><strong>Output: [1,7]
</strong></code></pre>

&#x20;

**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`

&#x20;

**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:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
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]};
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###