Description
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
Solutions
Solution 1: Enumeration
We design a function f(x) that returns two numbers whose product equals x and the absolute difference between these two numbers is the smallest. We can start enumerating i from √x. If x can be divided by i, then x⁄i is another factor. At this point, we have found two factors whose product equals x. We can return them directly. Otherwise, we decrease the value of i and continue to enumerate.
Next, we only need to calculate f(num + 1) and f(num + 2) respectively, and then compare the return values of the two functions. We return the one with the smaller absolute difference.
The time complexity is O(√num), and the space complexity is O(1). Where num is the given integer.
class Solution: def closestDivisors(self, num: int) -> List[int]: def f(x): for i in range(int(sqrt(x)), 0, -1): if x % i == 0: return [i, x // i] a = f(num + 1) b = f(num + 2) return a if abs(a[0] - a[1]) < abs(b[0] - b[1]) else b(code-box)
