Skip to content

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

Thinking

Find a factor pair of \(num+1\) or \(num+2\) with the smallest gap. \(num \le 10^9\) forbids scanning up to \(x\). The closest pair sits near \(\sqrt{x}\), so we walk downward from \(\lfloor\sqrt{x}\rfloor\) until a divisor appears. Do this for both \(num+1\) and \(num+2\) and keep the tighter pair.

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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};
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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
}

Comments