Skip to main content
Talentd

Closest Divisors - Solution & Explanation

MediumMath14 min readAsked at: Amazon
Practice this problem

Problem Statement

Given an integer num, find the closest two integers in absolute difference whose product equals num + 1 or num + 2.

Return the two integers in any order.

 

Example 1:

Input: num = 8
Output: [3,3]
Explanation: For num + 1 = 9, the closest divisors are 3 & 3, for num + 2 = 10, the closest divisors are 2 & 5, hence 3 & 3 is chosen.

Example 2:

Input: num = 123
Output: [5,25]

Example 3:

Input: num = 999
Output: [40,25]

 

Constraints:

  • 1 <= num <= 10^9

Approach Overview

Problem Overview: Given an integer num, find two integers whose product equals either num + 1 or num + 2. Among all valid pairs, return the pair with the smallest absolute difference. The task reduces to finding divisor pairs that are as close as possible.

Approach 1: Iterative Minimization Approach (O(sqrt(n)) time, O(1) space)

Compute divisors for both num + 1 and num + 2. For each value, iterate from 1 to sqrt(n). Whenever i divides the number, you get a pair (i, n / i). Track the pair with the smallest difference across both numbers. This works because divisor pairs naturally mirror around the square root, so scanning up to sqrt(n) guarantees finding all candidates.

This approach is straightforward and easy to reason about. The loop runs at most sqrt(num + 2) iterations for each candidate number, giving overall O(sqrt(n)) time and O(1) space. It fits naturally within math and number theory patterns commonly seen in divisor problems.

Approach 2: Square Root Approximation Approach (O(sqrt(n)) time, O(1) space)

The smallest difference between two divisors occurs when the pair is closest to the square root. Instead of scanning upward, start from floor(sqrt(num + 2)) and move downward. For each candidate divisor d, check if it divides num + 1 or num + 2. The first valid pair found produces the closest divisors because you are searching from the midpoint where factors are naturally closest.

This optimization avoids tracking multiple candidates and usually terminates quickly in practice. As soon as a valid divisor is found, the pair (d, target / d) is guaranteed to have the minimum difference for that target. Time complexity remains O(sqrt(n)) in the worst case with O(1) space, but average runtime is smaller due to early termination.

Recommended for interviews: The square root approximation approach is the one interviewers expect. It shows that you understand divisor symmetry around sqrt(n) and can minimize the search space effectively. The iterative scan demonstrates correct reasoning, but starting from the square root highlights deeper insight into math based optimization.

Approach 1: Square Root Approximation Approach

To find two numbers whose product is either num + 1 or num + 2, we can utilize the fact that such numbers will be around the square root of these sums. This is due to the mathematical property that for two numbers to multiply to a product, they will be closest when both numbers are as near as possible to the square root of the product.

This C program iterates over num + 1 and num + 2. For each number, it starts from its square root and moves downward to find the closest divisors.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(sqrt(num)) for each of num + 1 and num + 2. Thus, O(sqrt(num)) overall.
Space Complexity: O(1) as only a fixed number of variables are used.

Try this approach in the editor →

Approach 2: Iterative Minimization Approach

Another approach involves iteratively finding divisors for num + 1 and num + 2 starting from 1 up to the square root, and tracking which pair has the smallest difference.

This C implementation scans from 1 to the square root of num + 1 and num + 2. It tracks the pair of divisors with the smallest difference.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(sqrt(num))
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Enumeration

We design a function f(x) that returns two numbers whose product equals x and the absolute difference between these two numbers is the smallest. We can start enumerating i from \sqrt{x}. If x can be divided by i, then \frac{x}{i} is another factor. At this point, we have found two factors whose product equals x. We can return them directly. Otherwise, we decrease the value of i and continue to enumerate.

Next, we only need to calculate f(num + 1) and f(num + 2) respectively, and then compare the return values of the two functions. We return the one with the smaller absolute difference.

The time complexity is O(\sqrt{num}), and the space complexity is O(1). Where num is the given integer.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Square Root Approximation Approach

Time Complexity: O(sqrt(num)) for each of num + 1 and num + 2. Thus, O(sqrt(num)) overall.
Space Complexity: O(1) as only a fixed number of variables are used.

Iterative Minimization Approach

Time Complexity: O(sqrt(num))
Space Complexity: O(1)

Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Minimization ApproachO(sqrt(n))O(1)When implementing a simple and easy-to-understand divisor scan
Square Root Approximation ApproachO(sqrt(n))O(1)Preferred approach when you want the closest divisor pair quickly

Video Solution

1362. Closest Divisors (Leetcode Medium) • Programming Live with Larry • 470 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Closest Divisors easy or hard?
Closest Divisors is rated Medium because the core idea requires recognizing that the closest divisor pair lies near the square root. Once that insight is applied, the implementation is short and runs in O(sqrt(n)) time.
Closest Divisors Python/Java solution
Most implementations compute divisors starting from the square root of num + 2 and move downward until a valid factor is found. This logic translates directly into Python, Java, C++, C#, and JavaScript using a simple loop and modulo checks.
How to solve Closest Divisors in O(n)?
A naive solution could check every number from 1 to n for divisibility, which would take O(n) time. A better strategy exploits divisor symmetry and only checks up to sqrt(n). Starting near the square root reduces unnecessary checks and keeps the runtime at O(sqrt(n)).
What is the best approach for Closest Divisors?
The square root approximation approach is the most efficient. Start from floor(sqrt(num + 2)) and move downward until you find a divisor of either num + 1 or num + 2. This works because divisor pairs closest to the square root produce the smallest difference. The algorithm runs in O(sqrt(n)) time with O(1) space.
Is Closest Divisors asked at Google/Amazon/Meta?
Closest Divisors represents a typical number theory and math optimization problem that appears in interviews at large tech companies. Variants involving divisor pairs, factor search, or square root optimization have shown up in interviews at companies like Amazon and Google.
What data structure is used in Closest Divisors?
The problem does not require complex data structures. It relies on mathematical properties of divisors and simple integer arithmetic. Only a few variables are needed to track candidate divisor pairs, giving constant space complexity.
What is the time complexity of Closest Divisors?
The optimal solution runs in O(sqrt(n)) time because it only checks potential divisors up to the square root of num + 2. Each check is constant time, and the algorithm uses O(1) extra space.

Ready to solve this problem?

Practice Closest Divisors with our built-in code editor and test cases.

Practice on FleetCode
Previous

Distinct Prime Factors of Product of Array