Closest Divisors — Medium Problem & Solution

Problem statement

Find two integers whose product is either num + 1 or num + 2 and whose difference is as small as possible.

Return them in ascending order.

Example 1

Input: num = 8
Output: [3,3]
Explanation: 9 = 3 × 3 is a perfect square, so the gap is 0.

Example 2

Input: num = 123
Output: [5,25]
Explanation: 125 = 5 × 25 has gap 20, beating 124 = 4 × 31 with gap 27.

Example 3

Input: num = 999
Output: [25,40]
Explanation: 1000 = 25 × 40 has gap 15; the best factorisation of 1001 is 13 × 77.

Constraints

• 1 <= num <= 10000000

How to solve Closest Divisors

There are only two candidate products. For each, the most balanced factor pair is found by walking down from the square root to the first divisor; then compare the two gaps.

Approach

1. For t in {num + 1, num + 2}: set w = floor(sqrt(t)) and decrement until t % w == 0.
2. The pair is [w, t / w], with gap t / w - w.
3. Return whichever pair has the smaller gap.

Why it works

For a fixed product, the gap t/d - d shrinks as d rises towards sqrt(t), so the largest divisor at or below the square root is the balanced one. Checking both targets is exhaustive because the statement allows exactly those two.

Complexity

• Time — O(sqrt(num))
• Space — O(1)

Pitfalls

• Floating-point sqrt can overshoot by one on a perfect square — guard with while (w * w > t) w--.
• Returning the pair for num + 1 without comparing against num + 2 misses the better answer roughly half the time.
• w = 1 always divides, so the loop always terminates.

Reference solution

Python

from typing import List

def closestDivisors(num: int) -> List[int]:
    def best_pair(t: int) -> List[int]:
        w = int(t ** 0.5)
        while w * w > t:
            w -= 1
        while t % w != 0:
            w -= 1
        return [w, t // w]

    a = best_pair(num + 1)
    b = best_pair(num + 2)
    return a if a[1] - a[0] <= b[1] - b[0] else b

JavaScript

var closestDivisors = function(num) {
    var bestPair = function(t) {
        var w = Math.floor(Math.sqrt(t));
        while (w * w > t) w--;
        while (t % w !== 0) w--;
        return [w, t / w];
    };
    var a = bestPair(num + 1);
    var b = bestPair(num + 2);
    return (a[1] - a[0] <= b[1] - b[0]) ? a : b;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Find the Winner of the Circular Game Medium
• Stone Game VII Medium
• Number of Ways to Divide a Long Corridor Medium
• Count Ways to Group Overlapping Ranges Medium
• Count Number of Ways to Place Houses Medium
• Count Number of Texts Medium