K-th Smallest Prime Fraction — Medium Problem & Solution

arr is sorted and holds 1 followed by distinct prime numbers. For every pair of indices i 0.

Difficulty: Medium
Topics: Arrays, Sorting, Binary Search, Heap
Asked at: Amazon, Google, Adobe
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

arr is sorted and holds 1 followed by distinct prime numbers. For every pair of indices i < j consider the fraction arr[i] / arr[j].

Return the k-th smallest of those fractions as [numerator, denominator].

Example 1

Input: arr = [1,2,3,5], k = 3
Output: [2,5]
Explanation: In order: 1/5, 1/3, 2/5, 1/2, 3/5, 2/3.

Example 2

Input: arr = [1,7], k = 1
Output: [1,7]
Explanation: Only one fraction exists.

Example 3

Input: arr = [1,2,3,5], k = 1
Output: [1,5]

Constraints

2 <= arr.length <= 1000
1 <= arr[i] <= 30000
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

How to solve K-th Smallest Prime Fraction

Generate every pair i < j, order them by cross-multiplication, and take the k-th.

Approach

Collect [arr[i], arr[j]] for all i < j.
Sort with the comparator a[0] · b[1] - b[0] · a[1].
Return the entry at index k - 1.

Why it works

Cross-multiplication keeps the comparison in exact integers — floating point would blur fractions that differ in the twelfth decimal. The values stay inside a 32-bit int because the largest product is 30000 × 30000 = 9 × 10^8. Distinctness of the primes guarantees no two fractions tie, so the k-th is unambiguous. A max-heap of size k, or a binary search on the value, brings this down to O(n log n) when the pair count is too large to hold.

Complexity

Time — O(n² log n)
Space — O(n²)

Pitfalls

Comparing with floating-point division loses precision on close fractions.
k is 1-based, so the answer sits at index k - 1.
Only pairs with i < j count, so no fraction is ever at least 1.

Reference solution

Python

from typing import List
from functools import cmp_to_key

def kthSmallestPrimeFraction(arr: List[int], k: int) -> List[int]:
    n = len(arr)
    pairs = [[arr[i], arr[j]] for i in range(n) for j in range(i + 1, n)]
    pairs.sort(key=cmp_to_key(lambda a, b: a[0] * b[1] - b[0] * a[1]))
    return pairs[k - 1]

JavaScript

var kthSmallestPrimeFraction = function(arr, k) {
    var n = arr.length, i, j;
    var pairs = [];
    for (i = 0; i < n; i++) {
        for (j = i + 1; j < n; j++) pairs.push([arr[i], arr[j]]);
    }
    pairs.sort(function(a, b) { return a[0] * b[1] - b[0] * a[1]; });
    return pairs[k - 1];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue