Closest Divisors

To find the closest divisors of num + 1 or num + 2, you can use the following algorithm:

  1. Calculate Targets: The two target numbers for which you need to find divisors are num + 1 and num + 2.

  2. Find Divisors: For each target number, find its divisors. Start from the square root of the target number and iterate downwards. If a number i divides the target number, then the divisors are i and target // i.

  3. Compare Differences: Compare the absolute differences between the divisors for both target numbers and choose the pair with the smaller absolute difference.

  4. Return Result: Return the divisors for the target number with the smaller absolute difference.

Here’s the code:

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

from math import sqrt

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        def find_divisors(target):
            for i in range(int(sqrt(target)), 0, -1):
                if target % i == 0:
                    return i, target // i

        target1, target2 = num + 1, num + 2
        div1 = find_divisors(target1)
        div2 = find_divisors(target2)

        # Choose the divisors with the smaller absolute difference
        if abs(div1[0] - div1[1]) < abs(div2[0] - div2[1]):
            return div1
        else:
            return div2

The above code calculates the divisors by starting from the square root and iterating downwards, ensuring an efficient calculation. The time complexity is O(sqrt(n)) for finding the divisors of each target, leading to an overall time complexity of O(sqrt(n)). The space complexity is O(1).