1392. The kth Smallest Divisor

For each query print the kth smallest divisor of n, or -1 if n has fewer than k divisors.

n = 12, k = 1 -> 1 divisors in order: 1 2 3 4 6 12 n = 12, k = 3 -> 3 n = 12, k = 6 -> 12 n = 12, k = 7 -> -1

## What most people try first

Test every value from 1 to n for divisibility, counting as you go. That is O(n), which is 10^12.

## One sqrt walk produces both halves already sorted

Walk d from 1 while d*d <= n. Each divisor d found on the way up goes into a list low, and its partner n/d goes into a list high. Then:

• low comes out in increasing order, because d increases;
• high comes out in decreasing order, because n/d decreases as d
• grows.

So the full sorted divisor list is low followed by high reversed, and no sorting step is needed at all:

n = 12 d=1 low=[1] high=[12] d=2 low=[1,2] high=[12,6] d=3 low=[1,2,3] high=[12,6,4] sorted: 1 2 3 then 4 6 12

## The index arithmetic, which is the whole difficulty

Let total = len(low) + len(high). Then

if k > total: -1 else if k <= len(low): low[k - 1] else: high[total - k]

The last line is the one to get right. The element of high at position total - k is correct because high is stored in decreasing order: the largest divisor, high[0], is the totalth smallest, so the kth smallest is at index total - k.

## The perfect square case

When n is a perfect square, d = sqrt(n) has itself as its partner. Adding it to both lists would count it twice, so it is added to low only. That is the if d != n/d guard, and n = 36 with k = 4 is a declared test for exactly it: the divisors are 1 2 3 4 6 9 12 18 36, nine of them, an odd count, which only happens for perfect squares.

## Overflow

n reaches 10^12, which does not fit in a signed 32-bit integer since INT_MAX is 2147483647, and the loop condition d * d <= n reaches 10^12 too. A 32-bit build answers -1 where the truth is a real divisor, because the truncated n has far fewer divisors. The number of divisors itself is small: the record below 10^12 is 6720, for 963761198400. In JavaScript all these stay below 2^53, so a plain Number is exact.

## Cost

O(sqrt(n)) per query, with O(sqrt(n)) memory for the two lists.

Constraints - `1 ≤ q ≤ 100` - `1 ≤ n ≤ 1000000000000` - `1 ≤ k ≤ 1000000`