Ranked Prime Ratios

Medium

You are given a strictly increasing array values: it starts with 1, and every other element is a distinct prime. You are also given an integer rank. For every pair of indices i < j, form the fraction values[i] / values[j]. All these fractions are distinct. Sort them in increasing order and find the rank-th one (1-based). Return it as [numerator, denominator], i.e. [values[i], values[j]]. Listing all O(n²) fractions is easy; try to find the answer faster.

Example 1

values=[1, 3, 7, 11], rank=4 → [1, 3]

All fractions in increasing order: 1/11, 1/7, 3/11, 1/3, 3/7, 7/11. The fourth is 1/3.

Example 2

values=[1, 2, 5], rank=3 → [1, 2]

The fractions are 1/5, 2/5, 1/2. The third and largest is 1/2.

Example 3

values=[1, 13], rank=1 → [1, 13]

Constraints

2 ≤ len(values) ≤ 1000
values[0] = 1 and every other element is prime
values is strictly increasing, values[i] ≤ 3·10⁴
1 ≤ rank ≤ n·(n − 1) / 2, where n = len(values)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Two Pointers Binary Search Sorting Heap (Priority Queue)

Similar problems

Nearest k Values Medium Studios for Recording Sessions Medium Triples Under a Limit Medium K-th Smallest in a Sorted Grid Medium Warm Every Cabin Medium

Input

values=[1, 3, 7, 11], rank=4

Expected

[1, 3]

Run checks the first 3 tests in your browser. Submit checks all 54 tests on the server, hidden ones included.