# 1362. Closest Divisors

## Description

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

## Solutions

Solution 1: Enumeration

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.

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

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

• 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


• func closestDivisors(num int) []int {
f := func(x int) []int {
for i := int(math.Sqrt(float64(x))); ; i-- {
if x%i == 0 {
return []int{i, x / i}
}
}
}
a, b := f(num+1), f(num+2)
if abs(a[0]-a[1]) < abs(b[0]-b[1]) {
return a
}
return b
}

func abs(x int) int {
if x < 0 {
return -x
}
return x
}