Watch 7 video solutions for Closest Divisors, a medium level problem involving Math. This walkthrough by Programming Live with Larry has 457 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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^9Problem 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 | Time | Space | When to Use |
|---|---|---|---|
| Iterative Minimization Approach | O(sqrt(n)) | O(1) | When implementing a simple and easy-to-understand divisor scan |
| Square Root Approximation Approach | O(sqrt(n)) | O(1) | Preferred approach when you want the closest divisor pair quickly |