Closest Divisors: Factor Pairs Nearest the Square Root

Given an integer num, find two integers whose product equals either num + 1 or num + 2, and whose absolute difference is as small as possible. Return the two integers as a pair.

This is LeetCode 1362: Closest Divisors, and it is a clean exercise in understanding how factor pairs relate to the square root of a number.

Why this problem matters

Closest Divisors teaches you a fundamental property of factor pairs that comes up across many math problems: for any positive integer, the pair of factors with the smallest difference is always the one closest to the square root. This is not just a trick for this problem. It is the reason trial division only needs to check up to sqrt(n), the reason rectangle-packing problems start from the square root, and the reason factorization algorithms use the same search direction.

The problem also reinforces a useful pattern for "pick the best among a small number of candidates." Rather than solving one complex optimization, you solve two simpler subproblems (find the closest factor pair for num + 1 and for num + 2) and compare the results. Breaking a problem into independent candidates and picking the best one is a technique that appears in many interview questions.

The key insight

For any number n, its factor pairs can be written as (d, n / d) where d divides n. When d is small, n / d is large, and the difference between them is huge. As d grows toward sqrt(n), the two factors converge, and the difference shrinks. Once d passes sqrt(n), you start getting the same pairs in reverse order.

So to find the factor pair with the smallest difference, you only need to start at floor(sqrt(n)) and walk downward until you find a value that divides n. The first divisor you hit gives you the closest pair.

Since the problem asks you to check two numbers (num + 1 and num + 2), you run this search on both and return whichever pair has the smaller difference.

The solution

def closestDivisors(num):
    for d in range(int((num + 2) ** 0.5), 0, -1):
        if (num + 1) % d == 0:
            return [d, (num + 1) // d]
        if (num + 2) % d == 0:
            return [d, (num + 2) // d]

The loop starts at floor(sqrt(num + 2)), which is the largest possible starting point since num + 2 is the bigger of the two candidates. From there it walks downward, checking whether d divides num + 1 or num + 2. The first hit gives the factor pair closest to the square root, which is guaranteed to have the smallest difference.

Why does checking both numbers in the same loop work? Because d is the same for both checks, and a smaller d always means a larger difference. The very first d that divides either candidate produces the optimal answer. There is no need to find the best pair for each candidate separately and then compare.

Visual walkthrough

Complexity analysis

The optimized approach runs in O(sqrt(num)) time because you start near sqrt(num + 2) and walk down. In the worst case you walk all the way to 1, but that is still only sqrt(num) steps. Space is O(1) since you only track the current divisor.

The building blocks

1. Searching from the square root downward

The core technique here is iterating from floor(sqrt(n)) down to 1 to find the first divisor. This is the same principle behind trial division for primality testing: if n has no divisor between 2 and sqrt(n), it is prime. Here you use the same scan direction, but you stop at the first divisor you find rather than checking all of them.

d = int(n ** 0.5)
while n % d != 0:
    d -= 1

This snippet finds the largest factor of n that does not exceed sqrt(n). The complementary factor is n // d, and together they form the closest pair.

2. Comparing two candidates

The problem gives you two numbers to check (num + 1 and num + 2). Rather than running two separate searches and comparing, you can interleave the checks inside a single loop. At each value of d, you test both candidates. The first match wins because a larger d always produces a smaller difference.

This "check multiple candidates in one pass" pattern is useful whenever you need the best result across a small fixed number of options.

Edge cases

• num = 1: The candidates are 2 and 3. sqrt(3) is about 1.7, so d starts at 1. Both 2 and 3 are divisible by 1, so the first check hits: (1, 2). That is correct.
• num = 2: Candidates are 3 and 4. Starting at d = 2, we check 3 % 2 (no) and 4 % 2 (yes), returning [2, 2].
• Perfect square candidate: If num + 1 or num + 2 is a perfect square, the loop finds it immediately. For example, num = 8 gives num + 1 = 9, and d = 3 divides 9 on the first try, returning [3, 3] with difference 0.
• Large num: The constraint is num up to 10^9. sqrt(10^9) is about 31,623. The loop runs at most that many iterations, which completes in microseconds.
• Prime candidate: If num + 1 is prime, no factor other than 1 will divide it. But num + 2 is even (since num + 1 is odd and prime means num + 1 is at least 3, making num + 2 even), so the loop will find a factor of num + 2 quickly. You never need to walk all the way down to 1 in practice.

From understanding to recall

The logic is clean: start at the square root, walk down, check both candidates. You probably see why it works right now. But in an interview, will you remember to check num + 2 as well as num + 1? Will you recall that starting from sqrt(num + 2) covers both candidates in one loop? Will you be sure the first hit is optimal?

These are small details, but they are exactly the kind of thing that slips away after a few days. Spaced repetition locks them in. You write the solution from scratch, verify it produces the right output, and repeat at increasing intervals. After a few reps, the square-root search pattern and the dual-candidate trick become second nature.

Related posts

• Count Primes - Another math problem built on the relationship between factors and the square root, using the Sieve of Eratosthenes to count primes efficiently
• Factorial Trailing Zeroes - Factor counting across a range, where you count powers of 5 rather than searching for the closest pair
• Happy Number - A different flavor of math problem that combines digit manipulation with cycle detection

CodeBricks turns problems like Closest Divisors into lasting knowledge. Each factor-finding pattern you drill becomes a building block you can assemble on demand, whether the interview question asks about divisors, primes, or rectangle dimensions. Spaced repetition makes sure the details stay sharp.