Finding the Closest Divisors

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

Hints:
Find the divisors of n+1 and n+2.
To find the divisors of a number, you only need to iterate to the square root of that number.

Find the divisors of n+1 and n+2

We can find the closet divisors for n+1 and n+2 respectively. Then, we can compare the absolute difference of both divisors and pick the smaller one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<int> closestDivisors(int num) {
        vector<int> r1 = findDivisor(num + 1);
        vector<int> r2 = findDivisor(num + 2);
        if (abs(r1[0] - r1[1]) < abs(r2[0] - r2[1])) {
            return r1;
        }
        return r2;
    }
 
private:
    vector<int> findDivisor(int num) {
        vector<int> r = {1, num};
        for (int i = 2; i * i <= num; ++ i) {
            if (num % i == 0) {
                r = {i, num / i};
            }
        }
        return r;
    }
};

class Solution {
public:
    vector<int> closestDivisors(int num) {
        vector<int> r1 = findDivisor(num + 1);
        vector<int> r2 = findDivisor(num + 2);
        if (abs(r1[0] - r1[1]) < abs(r2[0] - r2[1])) {
            return r1;
        }
        return r2;
    }

private:
    vector<int> findDivisor(int num) {
        vector<int> r = {1, num};
        for (int i = 2; i * i <= num; ++ i) {
            if (num % i == 0) {
                r = {i, num / i};
            }
        }
        return r;
    }
};

We can start from the square root in the non-ascending order, thus enabling us early exit if we find a divisor. An improvement is to check (x+1) first then (x+2) since the first found divisor is the answer, we can safely exit the loop.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    vector<int> closestDivisors(int x) {
        for (int a = sqrt(x + 2); a > 0; --a) {
            if ((x + 1) % a == 0)
                return {a, (x + 1) / a};
            if ((x + 2) % a == 0)
                return {a, (x + 2) / a};
        }
        return {};
    }
};

class Solution {
public:
    vector<int> closestDivisors(int x) {
        for (int a = sqrt(x + 2); a > 0; --a) {
            if ((x + 1) % a == 0)
                return {a, (x + 1) / a};
            if ((x + 2) % a == 0)
                return {a, (x + 2) / a};
        }
        return {};
    }
};

Only the divisors up to Square Root of N are checked thus the runtime complexity of above solutions are O(Sqrt(N)).

–EOF (The Ultimate Computing & Technology Blog) —