Welcome to Subscribe On Youtube

1362. Closest Divisors

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 $\sqrt{x}$. If $x$ can be divided by $i$, then $\frac{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(\sqrt{num})$, and the space complexity is $O(1)$. Where $num$ is the given integer.

• Java
• C++
• Python
• Go

• class Solution {
      public int[] closestDivisors(int num) {
          int[] a = f(num + 1);
          int[] b = f(num + 2);
          return Math.abs(a[0] - a[1]) < Math.abs(b[0] - b[1]) ? a : b;
      }
  
      private int[] f(int x) {
          for (int i = (int) Math.sqrt(x);; --i) {
              if (x % i == 0) {
                  return new int[] {i, x / i};
              }
          }
      }
  }
  

• 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