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.
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.
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.
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.
Time Complexity: O(sqrt(num))
Space Complexity: O(1)
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.
| Approach | Complexity |
|---|---|
| Square Root Approximation Approach | Time Complexity: O(sqrt(num)) for each of |
| Iterative Minimization Approach | Time Complexity: O(sqrt(num)) |
| Enumeration | — |
| 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 |
1362. Closest Divisors (Leetcode Medium) • Programming Live with Larry • 457 views views
Watch 6 more video solutions →Practice Closest Divisors with our built-in code editor and test cases.
Practice on FleetCode