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
Solution: Brute Force
Time complexity: O(sqrt(n))
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: vector<int> closestDivisors(int num) { auto divisors = [](int n) { for (int i = sqrt(n); i >= 2; --i) if (n % i == 0) return vector<int>{i, n / i}; return vector<int>{1, n}; }; auto ans1 = divisors(num + 1); auto ans2 = divisors(num + 2); return ans1[1] - ans1[0] < ans2[1] - ans2[0] ? ans1 : ans2; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 |
# Author: Huahua class Solution: def closestDivisors(self, num: int) -> List[int]: def divisors(n: int) -> List[int]: for i in range(int(math.sqrt(n)), 1, -1): if n % i == 0: return [i, n // i] return [1, n] a1, a2 = divisors(num + 1), divisors(num + 2) return a1 if a1[1] - a1[0] < a2[1] - a2[0] else a2 |