Question

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.

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

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

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
}