Scale Engineer

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.

class Solution {    public int[] closestDivisors(int num) {        int[] pair1 = findClosest(num + 1);        int[] pair2 = findClosest(num + 2);         if (Math.abs(pair1[0] - pair1[1]) < Math.abs(pair2[0] - pair2[1])) {            return pair1;        } else {            return pair2;        }    }     // This helper function is inefficient and will time out.    private int[] findClosest(int n) {        int[] bestPair = {1, n};        int minDiff = n - 1;         for (int i = 2; i * i <= n; i++) { // A slightly better O(sqrt(n)) brute force            if (n % i == 0) {                int j = n / i;                if (Math.abs(i - j) < minDiff) {                    minDiff = Math.abs(i - j);                    bestPair[0] = i;                    bestPair[1] = j;                }            }        }        return bestPair;    }}

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.

Solutions

class 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 }; } } } }

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 →

Next problem