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.

Description Hints 2 Solution Video 6:01

1362. Closest Divisors

Medium64.3% acceptance1 company

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

Asked at 1 company

Amazon

Topics

Math

Hints open one at a time

Hint 1

Find the divisors of n+1 and n+2.

Hint 2

To find the divisors of a number, you only need to iterate to the square root of that number.

6:01

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution