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.

Examples

Example 1

1
2
3

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

1
2

Input: num = 123
Output: [5,25]

Example 3

1
2

Input: num = 999
Output: [40,25]

Constraints

  • 1 <= num <= 10^9

Solution

Method 1 – Factor Search from Square Root

Intuition

The closest divisors of a number are the pair of factors whose product is the number and whose difference is minimized. For a given number, the closest pair will be found near its square root.

Approach

  1. For both num + 1 and num + 2, search for a pair of divisors (a, b) such that a * b = num + 1 or a * b = num + 2.
  2. Start from the integer square root of the number and search downwards for the first divisor.
  3. For each candidate, compute the other factor and track the pair with the smallest absolute difference.
  4. Compare the best pairs for num + 1 and num + 2 and return the one with the smallest difference.

Code

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

class Solution {
public:
    vector<int> closestDivisors(int num) {
        auto get = [](int n) {
            for (int i = sqrt(n); i >= 1; --i) {
                if (n % i == 0) return vector<int>{i, n / i};
            }
            return vector<int>{1, n};
        };
        auto a = get(num + 1), b = get(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

func closestDivisors(num int) []int {
    get := func(n int) []int {
        for i := int(math.Sqrt(float64(n))); i >= 1; i-- {
            if n%i == 0 {
                return []int{i, n / i}
            }
        }
        return []int{1, n}
    }
    a := get(num + 1)
    b := get(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 }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int[] closestDivisors(int num) {
        int[] a = get(num + 1), b = get(num + 2);
        return Math.abs(a[0] - a[1]) <= Math.abs(b[0] - b[1]) ? a : b;
    }
    private int[] get(int n) {
        for (int i = (int)Math.sqrt(n); i >= 1; --i) {
            if (n % i == 0) return new int[]{i, n / i};
        }
        return new int[]{1, n};
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun closestDivisors(num: Int): IntArray {
        fun get(n: Int): IntArray {
            for (i in Math.sqrt(n.toDouble()).toInt() downTo 1) {
                if (n % i == 0) return intArrayOf(i, n / i)
            }
            return intArrayOf(1, n)
        }
        val a = get(num + 1)
        val b = get(num + 2)
        return if (kotlin.math.abs(a[0] - a[1]) <= kotlin.math.abs(b[0] - b[1])) a else b
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def closestDivisors(self, num: int) -> list[int]:
        def get(n: int) -> list[int]:
            for i in range(int(n ** 0.5), 0, -1):
                if n % i == 0:
                    return [i, n // i]
            return [1, n]
        a = get(num + 1)
        b = get(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
16
17

impl Solution {
    pub fn closest_divisors(num: i32) -> Vec<i32> {
        fn get(n: i32) -> Vec<i32> {
            let mut i = (n as f64).sqrt() as i32;
            while i > 0 {
                if n % i == 0 {
                    return vec![i, n / i];
                }
                i -= 1;
            }
            vec![1, n]
        }
        let a = get(num + 1);
        let b = get(num + 2);
        if (a[0] - a[1]).abs() <= (b[0] - b[1]).abs() { a } else { b }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    closestDivisors(num: number): number[] {
        function get(n: number): number[] {
            for (let i = Math.floor(Math.sqrt(n)); i >= 1; --i) {
                if (n % i === 0) return [i, n / i];
            }
            return [1, n];
        }
        const a = get(num + 1), b = get(num + 2);
        return Math.abs(a[0] - a[1]) <= Math.abs(b[0] - b[1]) ? a : b;
    }
}

Complexity

  • ⏰ Time complexity: O(sqrt(num))
  • 🧺 Space complexity: O(1)