# Closest Divisors
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/closest-divisors)
Canonical: https://scaleengineer.com/dsa/problems/closest-divisors
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## Problem
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
## Brute Force by Checking Divisors
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.
**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.
**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.
### Explanation
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`.

```java
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.*
### 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.

## Optimized Search from Square Root
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)`.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int[] closestDivisors(int num) {
        int[] pair1 = findClosestPair(num + 1);
        int[] pair2 = findClosestPair(num + 2);

        if (pair1[1] - pair1[0] < pair2[1] - pair2[0]) {
            return pair1;
        } else {
            return pair2;
        }
    }

    private int[] findClosestPair(int n) {
        int sqrtN = (int) Math.sqrt(n);
        for (int i = sqrtN; i >= 1; i--) {
            if (n % i == 0) {
                return new int[]{i, n / i};
            }
        }
        // This part is technically unreachable for n > 1, as 1 is always a divisor.
        return new int[]{1, 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.

# Solutions
### Java

```java
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 }; } } } }
```

### CPP

```cpp
class Solution {
public:
  vector<int> closestDivisors(int num) {
    auto f = [](int x) {
      for (int i = sqrt(x);; --i) {
        if (x % i == 0) {
          return vector<int>{i, x / i};
        }
      }
    };
    vector<int> a = f(num + 1);
    vector<int> b = f(num + 2);
    return abs(a[0] - a[1]) < abs(b[0] - b[1]) ? a : b;
  }
};

```

### Python

```python
class Solution:
    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

```