K-th Smallest Prime Fraction

Medium
973.

K-th Smallest Prime Fraction

K-th Smallest Prime Fraction is a medium coding problem on arrays, sorting and binary search, asked in Amazon, Google and Adobe interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */
var kthSmallestPrimeFraction = function(arr, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

K-th Smallest Prime Fraction — Problem & Solution

K-th Smallest Prime Fraction solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

K-th Smallest Prime Fraction is a medium coding problem on arrays, sorting and binary search, asked in Amazon, Google and Adobe interviews.

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

Hints for K-th Smallest Prime Fraction

  1. Hint 1

    Compare two fractions without dividing: a/b < c/d exactly when a·d < c·b, since everything is positive.

  2. Hint 2

    There are at most about half a million pairs, so building them all and sorting is affordable.

  3. Hint 3

    No two fractions are equal, because the values are 1 and distinct primes.

How to solve K-th Smallest Prime Fraction

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

Approach

  1. Collect [arr[i], arr[j]] for all i < j.
  2. Sort with the comparator a[0] · b[1] - b[0] · a[1].
  3. 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]

Java

public static int[] kthSmallestPrimeFraction(int[] arr, int k) {
    int n = arr.length;
    List<int[]> pairs = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) pairs.add(new int[] { arr[i], arr[j] });
    }
    pairs.sort((a, b) -> a[0] * b[1] - b[0] * a[1]);
    return pairs.get(k - 1);
}

C++

vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
    int n = (int) arr.size();
    vector<pair<int,int>> pairs;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) pairs.push_back({ arr[i], arr[j] });
    }
    sort(pairs.begin(), pairs.end(), [](const pair<int,int>& a, const pair<int,int>& b) {
        return (long long) a.first * b.second < (long long) b.first * a.second;
    });
    return { pairs[k - 1].first, pairs[k - 1].second };
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms