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

Try it yourself

Try solving this question here: