Find the k-th smallest fraction formed by choosing two numbers from a sorted prime array, where the numerator must come before the denominator.
K-th Smallest Prime Fraction
gfgProblem
You are given a strictly increasing array of positive integers arr, where arr[0] = 1 and the remaining values are prime numbers.
Consider all fractions of the form arr[i] / arr[j] such that 0 <= i < j < arr.length.
Your task is to return the fraction that is the k-th smallest when all such fractions are ordered from smallest to largest.
Notes
- Fractions are compared by their numerical value, not by numerator or denominator size.
- The answer should be returned as the numerator and denominator values from the array, not as a decimal.
- The array is already sorted in increasing order, which can be used to design an efficient solution.
Input Format
- An integer array
arrin strictly increasing order. - An integer
krepresenting the rank of the target fraction among all valid fractionsarr[i] / arr[j]withi < j.
Output Format
- Return the fraction as two integers:
[numerator, denominator]corresponding to thek-th smallest valid fraction.
Constraints
arr[0] = 1arris strictly increasing- All values after the first are prime numbers
1 <= k <= n(n-1)/2, wheren = arr.length- Use integer arithmetic carefully to avoid precision issues when comparing fractions.
Example 1
Input
arr = [1, 2, 3, 5], k = 3
Output
[2, 5]
Explanation
The valid fractions are 1/5, 1/3, 2/5, 1/2, 3/5, and 2/3. Sorted in increasing order, the 3rd smallest is 2/5.
Example 2
Input
arr = [1, 7], k = 1
Output
[1, 7]
Explanation
There is only one valid fraction, so it is automatically the 1st smallest.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.