LeetCode 1362 - Closest Divisors

LeetCode Problem 1362

Difficulty: 🟡 Medium
Topics: Math

Solution

Problem Understanding

The problem gives us an integer num, and asks us to find two integers whose product equals either num + 1 or num + 2, such that the absolute difference between the two integers is as small as possible.

In simpler terms, we are looking for a factor pair of either num + 1 or num + 2, and among all valid pairs we want the one whose values are closest together.

For example, if num = 8, then:

• num + 1 = 9, whose divisors include (1,9) and (3,3)
• num + 2 = 10, whose divisors include (1,10) and (2,5)

Since (3,3) has a difference of 0, which is smaller than the difference for (2,5), the answer is [3,3].

The input consists of a single integer num. The output should be a pair of integers whose multiplication equals either num + 1 or num + 2. The order does not matter, so [25,5] and [5,25] are both valid.

The constraints are important:

• 1 <= num <= 10^9

A naive algorithm that checks every divisor up to num would be too slow because num can be as large as one billion. This strongly suggests that we need a more mathematical observation to reduce the search space.

An important property of divisors is that the closest factor pair of a number is always near its square root. This observation will be the key to an efficient solution.

There are also some important edge cases:

• Very small numbers, such as num = 1, where num + 1 = 2 and num + 2 = 3, both prime numbers.
• Large values near 10^9, where an inefficient divisor search would time out.
• Cases where one candidate (num + 1) is prime while the other (num + 2) has a good factorization.
• Perfect squares, where the optimal answer may have equal divisors, such as (3,3) for 9.

The problem guarantees that num >= 1, so we never need to handle zero or negative values.

Approaches

Brute Force Approach

A straightforward solution is to examine every possible divisor for both num + 1 and num + 2.

For each target number:

1. Iterate through all integers from 1 to the number itself.
2. Check whether the integer divides the target evenly.
3. If it does, compute the paired divisor.
4. Track the pair with the smallest absolute difference.

After processing both numbers, return the best pair.

This approach works because it exhaustively checks every valid factor pair. Since every divisor is examined, the closest pair will definitely be found.

However, this method is far too slow for the constraint 10^9. In the worst case, iterating up to the number itself requires roughly one billion operations, which is impractical.

Optimal Approach

The key mathematical insight is that the closest divisor pair of a number is always closest to its square root.

Suppose a number n has divisors (a, b) where:

$$a \times b = n$$

If a and b are close together, they must both lie near √n.

For example:

• 36 → (6,6) near √36 = 6
• 40 → (5,8) near √40 ≈ 6.3

Instead of checking all divisors from 1 upward, we can:

1. Start from ⌊√n⌋
2. Move downward until we find a divisor
3. Return the pair immediately

Why does this work? Because the first divisor encountered below the square root automatically produces the closest possible pair.

Since we only check numbers down to the square root, the runtime becomes O(√n) instead of O(n).

We repeat this process for both num + 1 and num + 2, then choose the pair with the smaller difference.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Checks every possible divisor
Optimal	O(√n)	O(1)	Starts at square root and finds closest factor pair quickly

Algorithm Walkthrough

1. Compute the two candidate numbers: num + 1 and num + 2.
2. Create a helper function that finds the closest divisor pair for a given number n.
3. Inside the helper function, compute ⌊√n⌋. This is the ideal starting point because divisor pairs closest together lie near the square root.
4. Iterate downward from the square root toward 1.
5. For each candidate divisor d, check whether n % d == 0.
6. As soon as a valid divisor is found:

• Set the paired divisor as n // d
• Return [d, n // d]

We can stop immediately because the first divisor found from the square root downward guarantees the minimum difference. 7. Run the helper function for both num + 1 and num + 2. 8. Compare the absolute differences of the two resulting pairs. 9. Return the pair with the smaller difference.

Why it works

The correctness comes from the mathematical property of factor pairs. For a number n, factor pairs become farther apart as one factor moves away from √n. Therefore, the divisor closest to √n produces the minimum absolute difference. By searching downward from the square root and stopping at the first valid divisor, we are guaranteed to find the closest divisor pair. Repeating this for both num + 1 and num + 2, then selecting the smaller difference, guarantees the correct final answer.

Python Solution

from typing import List
import math

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        def find_closest_pair(n: int) -> List[int]:
            root = int(math.sqrt(n))

            for divisor in range(root, 0, -1):
                if n % divisor == 0:
                    return [divisor, n // divisor]

            return [1, n]

        pair1 = find_closest_pair(num + 1)
        pair2 = find_closest_pair(num + 2)

        diff1 = abs(pair1[0] - pair1[1])
        diff2 = abs(pair2[0] - pair2[1])

        return pair1 if diff1 <= diff2 else pair2

The implementation begins by defining a helper function, find_closest_pair, which computes the closest divisor pair for a given number.

Inside this helper, we first compute the integer square root of n. Starting from this point is important because divisor pairs nearest the square root are guaranteed to have the smallest difference.

We then iterate downward from the square root. The first time we find a divisor that evenly divides n, we immediately return the pair [divisor, n // divisor]. Since we are searching from the optimal region first, no later pair can be closer.

Back in the main method, we evaluate both candidate values, num + 1 and num + 2. We compute the difference between each pair and return the one with the smaller absolute gap.

The fallback return statement in the helper function is technically unnecessary because every positive integer is divisible by 1, but it keeps the function structurally complete.

Go Solution

package main

import "math"

func closestDivisors(num int) []int {
	findClosestPair := func(n int) []int {
		root := int(math.Sqrt(float64(n)))

		for divisor := root; divisor >= 1; divisor-- {
			if n%divisor == 0 {
				return []int{divisor, n / divisor}
			}
		}

		return []int{1, n}
	}

	pair1 := findClosestPair(num + 1)
	pair2 := findClosestPair(num + 2)

	diff1 := abs(pair1[0] - pair1[1])
	diff2 := abs(pair2[0] - pair2[1])

	if diff1 <= diff2 {
		return pair1
	}

	return pair2
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

The Go implementation follows exactly the same logic as the Python version. Since Go does not have a built-in absolute value function for integers, we implement a small helper function abs.

The square root calculation uses math.Sqrt, which requires converting the integer into float64, then converting the result back to int.

Slices are used for returning divisor pairs because Go does not have a lightweight list type like Python. The algorithm still uses constant extra space since only a few integers and tiny slices are allocated.

Worked Examples

Example 1

Input: num = 8

We evaluate:

• num + 1 = 9
• num + 2 = 10

Checking 9

Step	Divisor	Valid?	Pair
Start at √9 = 3	3	Yes	(3,3)

We stop immediately.

Checking 10

Step	Divisor	Valid?	Pair
Start at √10 = 3	3	No	-
Next	2	Yes	(2,5)

Comparison:

Pair	Difference
(3,3)	0
(2,5)	3

Final answer: [3,3]

Example 2

Input: num = 123

We evaluate:

• 124
• 125

Checking 124

Step	Divisor	Valid?	Pair
√124 = 11	11	No	-
10	No	-
9	No	-
8	No	-
7	No	-
6	No	-
5	No	-
4	Yes	(4,31)

Difference = 27

Checking 125

Step	Divisor	Valid?	Pair
√125 = 11	11	No	-
10	No	-
9	No	-
8	No	-
7	No	-
6	No	-
5	Yes	(5,25)

Difference = 20

Since 20 < 27, return:

[5,25]

Example 3

Input: num = 999

We evaluate:

• 1000
• 1001

Checking 1000

Step	Divisor	Valid?	Pair
√1000 = 31	31	No	-
30	No	-
29	No	-
28	No	-
27	No	-
26	No	-
25	Yes	(25,40)

Difference = 15

Checking 1001

Step	Divisor	Valid?	Pair
√1001 = 31	31	No	-
30	No	-
...	...	...	...
13	Yes	(13,77)

Difference = 64

Since 15 < 64, return:

[25,40]

The problem accepts any order, so [40,25] is also valid.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(√n)	We search downward from the square root for both num + 1 and num + 2
Space	O(1)	Only a few variables are used

Although we process two numbers, num + 1 and num + 2, this is still constant work, so the asymptotic complexity remains O(√n). Since √10^9 ≈ 31623, the algorithm runs efficiently even at the maximum constraint.

Test Cases

sol = Solution()

assert sol.closestDivisors(8) == [3, 3]  # perfect square candidate
assert sol.closestDivisors(123) == [5, 25]  # example case
assert sol.closestDivisors(999) in ([25, 40], [40, 25])  # order does not matter

assert sol.closestDivisors(1) in ([1, 2], [1, 3])  # smallest input
assert sol.closestDivisors(2) == [2, 2]  # num + 2 = 4

assert sol.closestDivisors(7) == [3, 3]  # num + 2 is perfect square
assert sol.closestDivisors(15) in ([4, 4], [4, 4])  # exact square

result = sol.closestDivisors(10**9)
assert result[0] * result[1] in (10**9 + 1, 10**9 + 2)  # large input

assert sol.closestDivisors(24) == [5, 5]  # num + 1 is perfect square
assert sol.closestDivisors(999999937)[0] * sol.closestDivisors(999999937)[1] in (
    999999938,
    999999939,
)  # large prime-like number

Test	Why
num = 8	Validates perfect square behavior
num = 123	Standard composite example
num = 999	Confirms comparison between num + 1 and num + 2
num = 1	Smallest valid input
num = 2	Ensures exact square selection
num = 7	Tests when num + 2 is a perfect square
num = 15	Tests equal divisor pair
num = 10^9	Verifies scalability at constraint limit
num = 24	Tests perfect square from num + 1
Large prime-like input	Stresses divisor search logic

Edge Cases

Very Small Input

When num = 1, we evaluate 2 and 3, both of which are prime numbers. The only valid divisor pairs are (1,2) and (1,3). A buggy implementation might assume a divisor larger than 1 always exists, but our algorithm safely falls back to 1 after searching downward.

Perfect Square Candidates

If either num + 1 or num + 2 is a perfect square, the optimal pair may have equal divisors. For example, num = 8 gives 9 = 3 × 3. Since equal numbers have difference 0, this is automatically optimal. Starting from the square root ensures we immediately find this case.

Large Numbers Near the Constraint Limit

For inputs close to 10^9, a brute-force approach becomes infeasible. Searching every divisor up to the number itself would take too long. Our implementation only checks numbers down to the square root, which limits the maximum iterations to roughly 31,623, keeping performance efficient.

Prime or Nearly Prime Numbers

Sometimes both num + 1 and num + 2 may have very few divisors. For example, if one candidate is prime, the only valid factorization is (1,n). The algorithm still behaves correctly because it eventually reaches 1, guaranteeing a valid divisor pair.