Problem Description

Given a positive integer num, find two positive integers a and b such that:

• Either a * b = num + 1 or a * b = num + 2
• The absolute difference |a - b| is minimized
• Return [a, b] as an array (or list) such that a ≤ b

There is always exactly one solution for every input num.

Constraints:

• 1 ≤ num ≤ 10^9

Thought Process

The problem asks us to find two divisors of either num + 1 or num + 2 whose product is exactly that number and whose difference is as small as possible. A brute-force approach would be to check all possible pairs, but this is inefficient for large numbers.

Noticing that the two numbers whose product is closest to a given number and whose difference is minimized will be closest to the square root of that number, we can optimize our approach. We only need to check divisors up to the square root of num + 1 and num + 2, as divisors come in pairs. For each candidate, we calculate the corresponding pair and track the pair with the smallest difference.

Solution Approach

Here is a step-by-step breakdown:

1. For both num + 1 and num + 2:
   • Iterate i from 1 up to sqrt(n) (where n is num + 1 or num + 2).
   • If i divides n exactly, then (i, n // i) is a valid pair.
   • Calculate the absolute difference |i - (n // i)| and track the pair with the smallest difference.
2. After checking both num + 1 and num + 2, return the pair that gives the smallest difference.
3. Ensure the returned pair is sorted so that a ≤ b.

This method is efficient because it only checks up to the square root of each candidate number, and thus runs quickly even for large inputs.

Example Walkthrough

Let's walk through an example with num = 8:

• Step 1: Compute num + 1 = 9 and num + 2 = 10.
• Step 2: For 9:
  • Divisors: 1 * 9, 3 * 3
  • Pairs: (1,9) (diff 8), (3,3) (diff 0)
• Step 3: For 10:
  • Divisors: 1 * 10, 2 * 5
  • Pairs: (1,10) (diff 9), (2,5) (diff 3)
• Step 4: The minimal difference is 0 for (3,3) in num + 1.
• Step 5: Return [3, 3].

Time and Space Complexity

• Brute-force approach: Would require checking all pairs up to num + 2, leading to O(N) time, which is not feasible for large num.
• Optimized approach: Only checks up to sqrt(num + 2) for each candidate (num + 1 and num + 2), so the time complexity is O(sqrt(N)).
• Space complexity is O(1) since only a few variables are used to track the best pair.

Summary

To find the closest divisors for num + 1 or num + 2, we leverage the fact that divisors closest to the square root will minimize the difference. By checking only up to the square root for both numbers, we efficiently find the optimal pair. This approach is both elegant and highly efficient, handling even the largest allowed inputs with ease.

Code Implementation

import math

class Solution:
    def closestDivisors(self, num: int):
        def get_closest(n):
            for i in range(int(math.isqrt(n)), 0, -1):
                if n % i == 0:
                    return [i, n // i]
        res1 = get_closest(num + 1)
        res2 = get_closest(num + 2)
        if abs(res1[0] - res1[1]) <= abs(res2[0] - res2[1]):
            return res1
        else:
            return res2
      

#include <vector>
#include <cmath>
using namespace std;

class Solution {
public:
    vector<int> getClosest(int n) {
        for (int i = (int)sqrt(n); i >= 1; --i) {
            if (n % i == 0) {
                return {i, n / i};
            }
        }
        return {};
    }
    vector<int> closestDivisors(int num) {
        vector<int> res1 = getClosest(num + 1);
        vector<int> res2 = getClosest(num + 2);
        if (abs(res1[0] - res1[1]) <= abs(res2[0] - res2[1]))
            return res1;
        else
            return res2;
    }
};
      

class Solution {
    public int[] closestDivisors(int num) {
        int[] res1 = getClosest(num + 1);
        int[] res2 = getClosest(num + 2);
        if (Math.abs(res1[0] - res1[1]) <= Math.abs(res2[0] - res2[1])) {
            return res1;
        } else {
            return res2;
        }
    }
    private int[] getClosest(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[0];
    }
}
      

var closestDivisors = function(num) {
    function getClosest(n) {
        for (let i = Math.floor(Math.sqrt(n)); i >= 1; --i) {
            if (n % i === 0) {
                return [i, n / i];
            }
        }
    }
    let res1 = getClosest(num + 1);
    let res2 = getClosest(num + 2);
    if (Math.abs(res1[0] - res1[1]) <= Math.abs(res2[0] - res2[1])) {
        return res1;
    } else {
        return res2;
    }
};