The kth Factor of n: Efficient Factor Enumeration

Given two positive integers n and k, return the kth factor of n in ascending order. If n has fewer than k factors, return -1.

This is LeetCode 1492: The kth Factor of n. A factor of n is any positive integer i such that n % i == 0. For example, the factors of 12 in ascending order are [1, 2, 3, 4, 6, 12], so for k = 3 the answer is 3.

Why this problem matters

Factor enumeration is one of the most fundamental operations in number theory and competitive programming. You will encounter it in problems involving divisors, GCDs, prime factorization, and combinatorics. Knowing how to enumerate factors efficiently is a building block that pays off repeatedly.

The naive approach of checking every number from 1 to n works, but it runs in O(n) time. For large values of n, this can be too slow. The key improvement is recognizing that factors come in pairs, which lets you cut the search space down to O(sqrt(n)). This sqrt optimization is a pattern you will see in many number theory problems.

The key insight

If i divides n, then n / i also divides n. These two divisors are on opposite sides of sqrt(n). For example, with n = 12: the pair (2, 6) satisfies 2 * 6 = 12, and 2 is below sqrt(12) while 6 is above it.

This means you only need to iterate i from 1 up to sqrt(n). For each i that divides n, you record both i (the small factor) and n / i (the large factor). After the loop, you have all the factors. Sort them, and pick the kth one. The total number of factors is at most 2 * sqrt(n), so sorting is fast.

The solution

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

The loop runs while i * i is at most n, which means i goes up to sqrt(n). For each divisor i, we also add n // i unless it equals i (which happens when n is a perfect square and i is the square root). After collecting all factors, we sort them and return the kth one using 0-based indexing (k - 1). If k exceeds the number of factors, we return -1.

Visual walkthrough

The brute-force approach scans every integer from 1 to n, checking divisibility one by one. The sqrt optimization cuts the work dramatically by exploiting the fact that divisors come in pairs. Both approaches produce the same result, but the sqrt version scales much better for large inputs.

Complexity analysis

The brute-force approach iterates through all numbers from 1 to n, checking each for divisibility. It uses O(1) space if you just count up to k without storing all factors. The sqrt approach iterates only up to sqrt(n), but needs O(sqrt(n)) space to store the collected factors before sorting. The sort itself takes O(sqrt(n) log sqrt(n)), which simplifies to O(sqrt(n) log n), but since the number of factors is small in practice, this is negligible.

The building blocks

1. Factor enumeration with sqrt

def get_factors(n):
    factors = []
    i = 1
    while i * i <= n:
        if n % i == 0:
            factors.append(i)
            if i != n // i:
                factors.append(n // i)
        i += 1
    return sorted(factors)

This is the reusable pattern. Iterate i from 1 while i * i does not exceed n. When n % i == 0, record both i and n // i. The guard i != n // i prevents adding the square root twice when n is a perfect square.

2. Pairing small and large factors

def kth_factor_no_sort(n, k):
    small = []
    large = []
    i = 1
    while i * i <= n:
        if n % i == 0:
            small.append(i)
            if i != n // i:
                large.append(n // i)
        i += 1
    # small is already sorted ascending
    # large is sorted descending, so reverse it
    all_factors = small + large[::-1]
    return all_factors[k - 1] if k <= len(all_factors) else -1

Since i increases during the loop, the small factors are already in ascending order. The large factors (n // i) decrease as i increases, so reversing that list gives you the remaining factors in ascending order. Concatenating the two lists produces all factors sorted without calling sort().

Edge cases

Before submitting, make sure your solution handles these:

• n = 1: The only factor is 1. For k = 1, return 1. For k = 2, return -1.
• k larger than number of factors: If n = 4 (factors: [1, 2, 4]) and k = 7, return -1.
• Perfect square: n = 16 has factors [1, 2, 4, 8, 16]. Note that 4 appears only once even though 4 * 4 = 16. The guard i != n // i handles this.
• Prime number: n = 13 has exactly two factors, [1, 13]. Any k greater than 2 returns -1.
• n equals k: Not necessarily related. n = 6, k = 6 would need 6 factors, but 6 only has 4 factors [1, 2, 3, 6], so return -1.
• k = 1: Always returns 1, since 1 is always the smallest factor of any positive integer.

From understanding to recall

You now know two approaches: brute-force iteration from 1 to n, and the sqrt optimization that collects factor pairs. The sqrt technique is the one worth memorizing, because it generalizes to any problem involving divisor enumeration.

The pattern is simple once you internalize it: loop while i * i does not exceed n, check n % i, record both i and n // i. But under time pressure, you need this to be automatic. Spaced repetition is the most reliable way to get there. Solve the problem today, revisit it in a few days, then again after a week. Each repetition strengthens the connection between "find divisors" and "loop to sqrt(n)."

Related posts

• Sqrt(x) - Binary search on integers
• Count Primes - Number theory with sieve
• Pow(x, n) - Efficient exponentiation

If you want to lock in these math patterns and build recall that lasts, try drilling them with spaced repetition. CodeBricks schedules reviews at the right intervals so the patterns stick.