Problem Statement

You are given a sorted list of numbers that includes the number 1 and unique prime numbers. You are also given an integer k.

For every pair of indexes i and j, where 0 <= i < j < arr.length, we consider the fraction arr[i] / arr[j].

Find the K-th smallest fraction from these pairs, and return this fraction as an array containing the numerator and the denominator.

Examples

Example 1

• Input: arr = [1, 3, 5], k = 3
• Output: [3, 5]
• Explanation: The fractions are 1/3, 1/5, and 3/5. The sorted order is 1/5, 1/3, and 3/5. The 3rd smallest fraction is 3/5.

Example 2

• Input: arr = [1, 3, 7, 11, 13], k = 5
• Output: [3, 11]
• Explanation: The fractions are 1/3, 1/7, 1/11, 1/13, 3/7, 3/11, 3/13, 7/11, 7/13, and 11/13. The sorted order is 1/13 < 1/11 < 1/7 < 3/13 < 3/11 < 1/3 < 3/7 < 7/13 < 7/11 < 11/13. The 5th smallest fraction is 3/13.

Example 3

• Input: arr = [1, 5, 7, 23], k = 2
• Output: [1, 7]
• Explanation: The fractions are 1/5, 1/7, 1/23, 5/7, 5/23, and 7/23. The sorted order is 1/23 < 1/7 < 1/5 < 5/23 < 7/23 < 5/7. The 2nd smallest fraction is 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

Solution

To solve this problem, we can use a min-heap (priority queue) to efficiently find the K-th smallest fraction. The heap will store fractions along with their indices in the array. By always pushing the next potential smallest fraction, we maintain an efficient way to access the K-th smallest fraction without sorting all possible fractions, which would be computationally expensive.

This approach ensures that we only consider the smallest fractions first and incrementally work our way up to the K-th smallest. The min-heap helps us keep track of the next smallest fraction to consider, ensuring that the algorithm is both efficient and straightforward.

Step-by-Step Algorithm

1. Initialize a min-heap to store fractions and their indices. The heap will use a comparator to keep the smallest fractions at the top.
2. Push initial fractions into the heap. For each element i from 0 to n-2, push the fraction (arr[i], arr[n-1]) into the heap.
3. Extract the smallest fraction from the heap K-1 times:
   • Pop the smallest fraction from the heap.
   • If frac[1] - 1 > frac[0], push the next fraction (frac[0], frac[1] - 1) into the heap.
4. Return the K-th smallest fraction. After K-1 extractions, the smallest fraction in the heap is the K-th smallest fraction.
5. Output the numerator and denominator of the K-th smallest fraction.

Algorithm Walkthrough

Input: arr = [1, 5, 7, 23], k = 2

1. Initial Fractions in Heap:

   • (1/23, indices 0,3)
   • (5/23, indices 1,3)
   • (7/23, indices 2,3)

2. First Extraction:

   • Extract smallest fraction: (1/23, indices 0,3)
   • Push next fraction: frac[1] - 1 > frac[0] = 3-1 > 0. So, push (1/7, indices 0,2) in the min-heap

3. Heap after first extraction:

   • (1/7, indices 0,2)
   • (5/23, indices 1,3)
   • (7/23, indices 2,3)

4. Second Extraction:

   • Extract smallest fraction: (1/7, indices 0,2)

5. Return [1, 7] as the 2nd smallest fraction.

Code