The kth Factor of n

medium math divisors

Problem

You are given two positive integers n and k. Imagine listing every factor of n — each integer from 1 to n that divides n with zero remainder — in increasing order. Return the kth entry of that list, or −1 if n has fewer than k factors. The constraints guarantee 1 ≤ k ≤ n ≤ 1000.

Inputn = 12, k = 3

Output3

The factors of 12 in ascending order are 1, 2, 3, 4, 6, 12, and the third one is 3.

n (1..144)

k (1..n)

def kth_factor(n, k):
    small, large = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            small.append(i)
            if i * i != n:
                large.append(n // i)
        i += 1
    factors = small + large[::-1]
    return factors[k - 1] if k <= len(factors) else -1

function kthFactor(n, k) {
  const small = [], large = [];
  for (let i = 1; i * i <= n; i++) {
    if (n % i === 0) {
      small.push(i);
      if (i * i !== n) large.push(n / i);
    }
  }
  const factors = small.concat(large.reverse());
  return k <= factors.length ? factors[k - 1] : -1;
}

int kthFactor(int n, int k) {
    List<Integer> small = new ArrayList<>();
    List<Integer> large = new ArrayList<>();
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            small.add(i);
            if (i * i != n) large.add(n / i);
        }
    }
    Collections.reverse(large);
    small.addAll(large);
    return k <= small.size() ? small.get(k - 1) : -1;
}

int kthFactor(int n, int k) {
    vector<int> small, large;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            small.push_back(i);
            if (i * i != n) large.push_back(n / i);
        }
    }
    small.insert(small.end(), large.rbegin(), large.rend());
    return k <= (int)small.size() ? small[k - 1] : -1;
}

Explanation

The brute-force answer scans every i from 1 to n and counts divisors, which is fine for n ≤ 1000 but misses the elegant structure: factors come in mirrored pairs. Whenever i divides n, so does n / i, and exactly one member of each pair is at most √n. So scanning just 1 … √n discovers every factor.

We keep two lists. Each divisor i found in the scan goes into small, and its partner n / i goes into large. If n is a perfect square, the divisor i = √n is its own mirror, so we add it only once to avoid a duplicate.

The lists come out pre-sorted for free: small is built in increasing order, while large receives partners in decreasing order (the partner of a growing i shrinks). Reversing large and appending it to small therefore yields the complete factor list in ascending order — no sorting step needed. The answer is the element at index k − 1, or −1 when fewer than k factors exist.

Walking the default example n = 12, k = 3: the scan tries i = 1, 2, 3 (stopping because 4² = 16 > 12). All three divide 12, giving small = [1, 2, 3] and mirrors large = [12, 6, 4]. Concatenating small with the reversed large list produces [1, 2, 3, 4, 6, 12], whose third entry is 3.

The loop runs ⌊√n⌋ times and every iteration does constant work, so time is O(√n). The two lists hold at most one pair per iteration, so space is also O(√n) — a real win over the O(n) scan once n grows large.

Time: O(√n) Space: O(√n)