Four Divisors: Efficient Divisor Counting

LeetCode 1390. Four Divisors gives you an integer array nums and asks you to return the sum of divisors of every integer in that array that has exactly four divisors. If no such integer exists, return 0.

Why this problem matters

Divisor enumeration is one of the most common math patterns in coding interviews. You will see it surface in problems about counting factors, finding perfect numbers, and checking prime-like properties. The core skill is the same every time: iterate up to the square root, pair up divisors, and avoid redundant work. Mastering this pattern once means you can apply it everywhere.

The key insight

You do not need to check every number from 1 to n to find all of n's divisors. If i divides n, then n / i also divides n. So you only need to iterate i from 1 to sqrt(n). For each valid i, you get two divisors at once (or one, if i * i == n). This cuts the work from O(n) per number down to O(sqrt(n)).

On top of that, you can bail out early. The moment you discover more than four divisors, you know this number does not qualify, and you can skip to the next one.

The solution

def sum_four_divisors(nums):
    total = 0
    for n in nums:
        divisors = []
        i = 1
        while i * i <= n:
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)
                if len(divisors) > 4:
                    break
            i += 1
        if len(divisors) == 4:
            total += sum(divisors)
    return total

For each number in the array, we find all its divisors by iterating from 1 up to its square root. Every time i divides n, we record both i and n // i (unless they are the same, which only happens for perfect squares). If we ever collect more than four divisors, we break out of the inner loop immediately. After checking all candidates for a given number, we add the divisor sum to our total only if the count is exactly four.

Visual walkthrough

The walkthrough shows how each number is examined independently. Numbers 6, 8, and 21 each have exactly four divisors, so their divisor sums (12, 15, and 32) are accumulated into the final answer of 59.

Complexity analysis

Here n is the length of the input array and max_val is the largest value in it. For each number, we do at most O(sqrt(max_val)) work. The space is O(1) beyond the input because we only track a small list of divisors (capped at 5 before we break) and a running total.

The building blocks

1. Divisor enumeration via square root

i = 1
while i * i <= n:
    if n % i == 0:
        divisors.append(i)
        if i != n // i:
            divisors.append(n // i)
    i += 1

This is the standard way to find all divisors of a number. You iterate i from 1 while i * i is at most n. Each time i divides n, you get the pair (i, n // i). The guard i != n // i avoids counting a perfect square root twice.

2. Early termination on count

if len(divisors) > 4:
    break

Once you have found more than four divisors, there is no point continuing. This number cannot qualify, so you skip the rest of the inner loop. Early termination is a general technique: any time you know the answer for a sub-problem, stop doing unnecessary work.

Edge cases

• Prime numbers: A prime p has exactly two divisors (1 and p), so it never qualifies.
• Perfect squares with few factors: A number like 4 has divisors [1, 2, 4], which is three, not four. Numbers like 9 have [1, 3, 9]. These do not qualify either.
• 1: Only has one divisor, [1]. Always skipped.
• Large values: The constraint allows values up to 10^5. The square root of 100,000 is about 316, so the inner loop runs at most a few hundred iterations per number.

From understanding to recall

Reading this solution is one thing. Reproducing it under time pressure in an interview is another. The divisor enumeration pattern and the early termination trick are both building blocks that appear in many problems. Drilling them individually with spaced repetition means they become second nature. When you encounter a new problem that asks "how many divisors does this number have?" or "find all factors efficiently," the square root loop will come to you automatically.

Related posts

• Count Primes - Another math problem that uses the square root boundary for efficiency
• Ugly Number III - Divisibility-based problem that combines math with binary search
• Happy Number - A number theory problem that requires careful digit manipulation

CodeBricks breaks every LeetCode problem into its fundamental building blocks and drills them using spaced repetition. Instead of re-reading solutions, you practice writing each piece from scratch at increasing intervals until it sticks.