Solution: Kth Smallest Prime Fraction

Statement

You are given a sorted array of unique integers, arr, which includes the number $1$ and other prime numbers. You are also given an integer $k$.

For every index $i$ and $j$ where $0 \leq i < j <$ arr.length, you can form a fraction by taking the number at index $i$ as the numerator and the number at index $j$ as the denominator, resulting in the fraction arr[i] / arr[j].

Your task is to return the $k^{th}$ smallest fraction among these fractions. The answer should be returned as an array of two integers, where the first element, answer[0], is the numerator (arr[i]), and the second element, answer[1], is the denominator (arr[j]) corresponding to the $k^{th}$ smallest fraction.

Constraints:

• $2 \leq$ arr.length $\leq 10^3$

• $1 \leq arr[i] \leq 3 \times 10^4$

• $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 \leq k \leq$ arr.length $\times$ (arr.length $- 1$)

Solution

We need to find the $k^{th}$ smallest fraction that can be formed using elements from a sorted array of unique integers (which includes 1 and prime numbers).

We first add the smallest possible fraction for each denominator into a heap. This fraction is formed by pairing the first element of the array with each later element. As the array is sorted, the smallest fraction for any denominator always has the first element as the numerator. Adding only these fractions ensures we process the smallest ones first.

Next, we repeatedly remove the smallest fraction from the heap. Each fraction belongs to a sequence where the denominator stays the same, but the numerator can increase. If a larger numerator exists in that sequence, we form the next fraction and insert it into the heap. This keeps the heap updated and ensures we always have the next smallest fraction available.

We repeat this process $k−1$ times, filtering out smaller fractions. The next fraction we remove is the $k^{th}$ smallest, our final answer.

Here are the detailed steps of the algorithm that we have just discussed:

1. We initialize an empty heap, minHeap, to store fractions in ascending order.

2. Next, we iterate over the input array, arr, from index $1 \space \text{to} \space n-1$ (denoted by $j$). For each arr[j], we form the smallest possible fraction using arr[0] as the numerator and arr[j] as the denominator. As arr is sorted, the smallest fraction for each denominator is always arr[0] / arr[j].

   1. At each iteration, we store the following three values in the min heap:

      1. A fraction value is denoted by arr[0] / arr[j].

      2. A numerator index is initially set to $0$, referring to arr[0].

      3. A denominator index, $j$, refers to arr[j].

   2. The fractions are inserted into minHeap, using their values as keys.

3. To identify the $k^{th}$ smallest fraction, we repeat the following process $k-1$ times:

   1. Extract the smallest fraction from minHeap, representing the next smallest fraction overall. Identify the numerator index i and denominator index j.

   2. If there is a larger fraction available from the same denominator group (i + 1 < j), compute arr[i + 1] / arr[j] and insert it into minHeap. This ensures the heap remains updated with the next candidate fraction.

4. After performing the above steps $k - 1$ times, we extract the top fraction from min_heap, which is the $k^{th}$ smallest fraction. So, we return its numerator and denominator as [arr[i], arr[j]].

The following illustration shows these steps in detail: