Leetcode 1362: Closest Divisors

Input: The input consists of an integer `num` which represents the given number.

Example: num = 8

Constraints:

• 1 <= num <= 10^9

Output: The output should be a list of two integers that have the smallest absolute difference, whose product is equal to `num + 1` or `num + 2`.

Example: [3, 3]

Constraints:

• The output will always contain exactly two integers.

Goal: To find the two closest divisors of `num + 1` or `num + 2` whose absolute difference is the smallest.

Steps:

• For each possible divisor from `sqrt(num + 2)` down to 1, check if it divides `num + 1` or `num + 2`.

• Once a divisor is found, return the pair of divisors with the smallest difference.

Goal: Ensure that the value of `num` satisfies the given constraints.

Steps:

• The input `num` must be between 1 and 10^9.

Assumptions:

• The input `num` is always a positive integer.

• Input: num = 8

• Explanation: For `num + 1 = 9`, the closest divisors are `3` and `3`, and for `num + 2 = 10`, the closest divisors are `2` and `5`. The pair `[3, 3]` is returned as it has the smallest absolute difference.

• Input: num = 25

• Explanation: For `num + 1 = 26`, the closest divisors are `2` and `13`, and for `num + 2 = 27`, the closest divisors are `3` and `9`. The pair `[5, 6]` is returned because it forms the closest divisors.

Approach: The approach involves iterating from the square root of `num + 2` down to 1, checking divisibility, and selecting the closest divisors with the smallest absolute difference.

Observations:

• The problem requires finding divisors of `num + 1` and `num + 2`.

• We can use the square root method to optimize the search for divisors.

• The main challenge is to ensure that the divisors have the smallest possible difference.

Steps:

• Initialize a loop to check divisors from `sqrt(num + 2)` down to 1.

• For each divisor, check if it divides `num + 1` or `num + 2`.

• Return the pair with the smallest difference as soon as it's found.

Empty Inputs:

• This problem does not involve empty inputs, as the input is always a positive integer.

Large Inputs:

• Ensure that the solution handles very large values of `num` up to 10^9 efficiently.

Special Values:

• Handle cases where `num + 1` or `num + 2` has only one divisor pair.

Constraints:

• Ensure that the solution works within the given constraints.

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

1 : Function Declaration

vector<int> closestDivisors(int num) {

The function 'closestDivisors' takes an integer 'num' and returns a vector containing two divisors of 'num+1' or 'num+2' whose product is closest to 'num'.

2 : For Loop Initialization

    for(int a = sqrt(num + 2); a > 0; a--) {

A for loop is initialized with 'a' starting from the square root of 'num + 2'. It iterates downwards, checking possible divisors of 'num+1' and 'num+2'.

3 : Divisor Check for num+1

        if((num + 1) % a == 0) return vector<int>{a, (num + 1) / a};

Checks if 'a' is a divisor of 'num+1'. If true, it returns a vector with 'a' and 'num+1' divided by 'a' as the divisors.

4 : Divisor Check for num+2

        if((num + 2) % a == 0) return vector<int>{a, (num + 2) / a};

Checks if 'a' is a divisor of 'num+2'. If true, it returns a vector with 'a' and 'num+2' divided by 'a' as the divisors.

5 : Return Empty Vector

    return vector<int>{};

If no divisors are found for 'num+1' or 'num+2', the function returns an empty vector.

Best Case: O(sqrt(num))

Average Case: O(sqrt(num))

Worst Case: O(sqrt(num))

Description: The time complexity is dominated by the need to check divisors up to the square root of `num + 2`.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is constant since only a few variables are used in the solution.

Leetcode 1362: Closest Divisors

Explore →