Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1362.html
1362. Closest Divisors
Level
Medium
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
Solution
Let num1 = num + 1
and num2 = num + 2
. Calculate the square roots of num1
and num2
respectively. For each number num1
and num2
, loop over 1 to the square root and find the maximum factor in the range such that the number is divisible by the factor. Suppose the maximum factor of num1
is factor1
and the maximum factor of num2
is factor3
. Let factor2 = num1 / factor1
and factor4 = num2 / factor3
. Calculate the absolute difference between factor2
and factor1
and the absolute difference between factor4
and factor3
, and return the two factors with a smaller absolute difference.
-
class Solution { public int[] closestDivisors(int num) { long num1 = num + 1, num2 = num + 2; long sqrt1 = (long) Math.sqrt(num1); long factor1 = 2; long factor1Max = 1; long sqrt2 = (long) Math.sqrt(num2); long factor3 = 2; long factor3Max = 1; while (factor1 <= sqrt1) { if (num1 % factor1 == 0) factor1Max = factor1; factor1++; } while (factor3 <= sqrt2) { if (num2 % factor3 == 0) factor3Max = factor3; factor3++; } factor1 = factor1Max; factor3 = factor3Max; long factor2 = num1 / factor1; long factor4 = num2 / factor3; if (Math.abs(factor2 - factor1) <= Math.abs(factor4 - factor3)) return new int[]{(int) factor1, (int) factor2}; else return new int[]{(int) factor3, (int) factor4}; } }
-
class Solution { public: vector<int> closestDivisors(int num) { auto f = [](int x) { for (int i = sqrt(x);; --i) { if (x % i == 0) { return vector<int>{i, x / i}; } } }; vector<int> a = f(num + 1); vector<int> b = f(num + 2); return abs(a[0] - a[1]) < abs(b[0] - b[1]) ? a : b; } };
-
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
-
func closestDivisors(num int) []int { f := func(x int) []int { for i := int(math.Sqrt(float64(x))); ; i-- { if x%i == 0 { return []int{i, x / i} } } } a, b := f(num+1), f(num+2) if abs(a[0]-a[1]) < abs(b[0]-b[1]) { return a } return b } func abs(x int) int { if x < 0 { return -x } return x }