Closest Divisors

Med

#1264Time: O(num). In the worst-case implementation, the helper function `findClosest` iterates up to `n`. Since we call it for `num + 1` and `num + 2`, the complexity is `O(num)`. Even with an optimization to iterate up to `sqrt(n)`, this implementation style is less efficient as it doesn't stop early. For the given constraints where `num` can be up to `10^9`, this approach is too slow.Space: O(1) extra space. We only use a few variables to store the candidate pairs and their differences.

Patterns

Math

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves a straightforward, yet inefficient, check of potential divisors for both num + 1 and num + 2. For each of these two numbers, we iterate from 1 up to the number itself (or n/2 as a small optimization) to find all pairs of divisors. Throughout the iteration, we keep track of the pair with the smallest absolute difference found so far.

Algorithm

Define a helper function findClosest(n) that finds the closest pair of divisors for a given integer n.
Inside findClosest(n):
- Initialize a bestPair with [1, n] and minDiff with n - 1.
- Iterate with a loop variable i from 2 up to n / 2.
- In each iteration, check if i is a divisor of n.
- If i is a divisor, calculate the other divisor j = n / i.
- Compare the new difference abs(i - j) with minDiff. If it's smaller, update minDiff and bestPair.
- After the loop, return bestPair.
Call the helper function to get the closest divisors for num + 1, let's call it pair1.
Call the helper function again to get the closest divisors for num + 2, let's call it pair2.
Compare the absolute difference of the elements in pair1 and pair2.
Return the pair with the smaller difference.

Walkthrough

The core idea is to find the closest pair of divisors for num + 1 and num + 2 separately and then compare the results to find the overall best pair. To find the closest divisors for a number x, we can iterate a variable i from 1 up to x. If i divides x, we've found a pair of divisors (i, x/i). We calculate the difference between them and compare it with the minimum difference found so far, updating our result if the new pair is closer. This process is repeated for both num + 1 and num + 2.

1class Solution {2    public int[] closestDivisors(int num) {3        int[] pair1 = findClosest(num + 1);4        int[] pair2 = findClosest(num + 2);5 6        if (Math.abs(pair1[0] - pair1[1]) < Math.abs(pair2[0] - pair2[1])) {7            return pair1;8        } else {9            return pair2;10        }11    }12 13    // This helper function is inefficient and will time out.14    private int[] findClosest(int n) {15        int[] bestPair = {1, n};16        int minDiff = n - 1;17 18        for (int i = 2; i * i <= n; i++) { // A slightly better O(sqrt(n)) brute force19            if (n % i == 0) {20                int j = n / i;21                if (Math.abs(i - j) < minDiff) {22                    minDiff = Math.abs(i - j);23                    bestPair[0] = i;24                    bestPair[1] = j;25                }26            }27        }28        return bestPair;29    }30}

Note: The provided code illustrates the concept. A naive loop up to n or n/2 would be even slower. Even with the i*i <= n optimization, finding the best pair this way is less efficient than the optimal approach because it continues searching after finding the first pair from the middle.

Complexity

Time

O(num). In the worst-case implementation, the helper function `findClosest` iterates up to `n`. Since we call it for `num + 1` and `num + 2`, the complexity is `O(num)`. Even with an optimization to iterate up to `sqrt(n)`, this implementation style is less efficient as it doesn't stop early. For the given constraints where `num` can be up to `10^9`, this approach is too slow.

Space

O(1) extra space. We only use a few variables to store the candidate pairs and their differences.

Trade-offs

Pros

Simple to understand and implement.
Logically straightforward.

Cons

Extremely inefficient for large numbers.
Will result in a 'Time Limit Exceeded' (TLE) error on most competitive programming platforms for the given constraints.

A much more efficient approach is to realize that for any pair of divisors (a, b) of a number n where a ≤ b, it must be that a ≤ sqrt(n). To find the pair with the smallest difference, a and b must be as close to sqrt(n) as possible. This means we should search for the largest divisor a that is less than or equal to sqrt(n), which can be found by searching downwards from sqrt(n).

Algorithm

Define a helper function findClosestPair(n) that finds the closest pair of divisors for n.
Inside findClosestPair(n):
- Calculate the integer part of the square root of n, let's call it s.
- Iterate with a loop variable i downwards from s to 1.
- In each iteration, check if i divides n evenly (n % i == 0).
- The first i that satisfies this condition gives the pair (i, n/i). Since we are iterating down from the square root, this pair is guaranteed to have the minimum difference.
- Return [i, n/i] immediately.
Call pair1 = findClosestPair(num + 1).
Call pair2 = findClosestPair(num + 2).
Compare the difference pair1[1] - pair1[0] with pair2[1] - pair2[0].
Return the pair with the smaller difference.

Walkthrough

The key insight is that if i is a divisor of n, then n/i is also a divisor. The difference |i - n/i| is minimized when i and n/i are close to each other, which occurs when both are near sqrt(n). Therefore, we can find the closest pair of divisors for a number x by starting our search for a divisor from floor(sqrt(x)) and iterating downwards. The very first divisor i we find will form the pair (i, x/i) with the smallest possible difference.

We apply this efficient method to both num + 1 and num + 2. After finding the closest pair for each, we compare their differences and return the overall best pair.

1class Solution {2    public int[] closestDivisors(int num) {3        int[] pair1 = findClosestPair(num + 1);4        int[] pair2 = findClosestPair(num + 2);5 6        if (pair1[1] - pair1[0] < pair2[1] - pair2[0]) {7            return pair1;8        } else {9            return pair2;10        }11    }12 13    private int[] findClosestPair(int n) {14        int sqrtN = (int) Math.sqrt(n);15        for (int i = sqrtN; i >= 1; i--) {16            if (n % i == 0) {17                return new int[]{i, n / i};18            }19        }20        // This part is technically unreachable for n > 1, as 1 is always a divisor.21        return new int[]{1, n}; 22    }23}

Complexity

Time

O(sqrt(num)). The `findClosestPair` function iterates from `sqrt(n)` down to 1. We call this for `num + 1` and `num + 2`. The total time complexity is dominated by these two calls, resulting in `O(sqrt(num + 1)) + O(sqrt(num + 2))`, which simplifies to `O(sqrt(num))`. This is very efficient for the given constraints.

Space

O(1) extra space. The algorithm uses a constant amount of space regardless of the input size.

Trade-offs

Pros

Highly efficient and optimal for this problem.
Easily passes time limits for large inputs due to its sub-linear time complexity.

Cons

Requires understanding the mathematical property that the closest divisors of a number are near its square root.

Solutions

Solution

1class Solution { public int [] closestDivisors ( int num ) { int [] a = f ( num + 1 ); int [] b = f ( num + 2 ); return Math . abs ( a [ 0 ] - a [ 1 ]) < Math . abs ( b [ 0 ] - b [ 1 ]) ? a : b ; } private int [] f ( int x ) { for ( int i = ( int ) Math . sqrt ( x );; -- i ) { if ( x % i == 0 ) { return new int [] { i , x / i }; } } } }

1class Solution {2public:3  vector<int> closestDivisors(int num) {4    auto f = [](int x) {5      for (int i = sqrt(x);; --i) {6        if (x % i == 0) {7          return vector<int>{i, x / i};8        }9      }10    };11    vector<int> a = f(num + 1);12    vector<int> b = f(num + 2);13    return abs(a[0] - a[1]) < abs(b[0] - b[1]) ? a : b;14  }15};

1class Solution:2    def closestDivisors(self, num: int) -> List[int]: def f(x): for i in range(int(sqrt(x)), 0, - 1): if x % i == 0: return [i, x // i] a = f(num + 1) b = f(num + 2) return a if abs(a[0] - a[1]) < abs(b[0] - b[1]) else b

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem