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.

• Java
• C++
• Python
• Go

• 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
  }
  

All Problems

All Solutions