[LeetCode] 1362. Closest Divisors 最接近的因数

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

这道题说是给了一个数字 num，让找 num+1 或者 num+2 数字的两个因子使得其差的绝对值最小。题意并不难理解，主要就是找给定数字的因子，然后比较其差的绝对值就行了。由于对 num+1 和 num+2 的操作是相同的，所以用一个子函数来实现比较好，找因子并不需要从1遍历到其本身，因为每对儿因子只要处理一次就行了，可以从其平方根遍历到1，对于遍历到的数字i，若其能被 num 整除，则计算两个因子i和 num/i 的差的绝对值，若其小于 diff，则用其来更新 diff，并且将这两个数字记录到 res 中，这样最终结果 res 中保存的就是差的绝对值最小的两个因子了。在主函数中，分别对 num+1 和 num+2 调用这个子函数，然后将得到的两组结果再次分别计算差的绝对值，返回较小的那组即可，参见代码如下：

解法一：

class Solution {
public:
    vector<int> closestDivisors(int num) {
        vector<int> res1 = find(num + 1), res2 = find(num + 2);
        return abs(res1[0] - res1[1]) < abs(res2[0] - res2[1]) ? res1 : res2;
    }
    vector<int> find(int num) {
        vector<int> res;
        int diff = INT_MAX;
        for (int i = sqrt(num); i > 0; --i) {
            if (num % i != 0) continue;
            if (abs(num / i - i) < diff) {
                diff = abs(num / i - i);
                res = {num / i, i};
            }
        }
        return res;
    }
};

其实这道题并不用遍历所有的因子组合，而是从平方根开始往1遍历，第一个找到的因子对儿就一定是差值最小的，为什么呢？因为若一个平方数，其两个平方根作为因子，差的绝对值为0，已经是最小的了，所以偏离平方根的因子的差的绝对值一定是越来越大的，所以找到的第一对儿因子就一定是满足题意的。这里我们从 num+2 的平方根开始往1遍历，对于每个遍历到的数字i，若其是 num+1 的因子，直接返回因子对儿，否则看下若其是 num+2 的因子，直接返回因子对儿即可，参见代码如下：

解法二：

class Solution {
public:
    vector<int> closestDivisors(int num) {
        for (int i = sqrt(num + 2); i > 0; --i) {
            if ((num + 1) % i == 0) {
                return {i, (num + 1) / i};
            }
            if ((num + 2) % i == 0) {
                return {i, (num + 2) / i};
            }
        }
        return {};
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1362

类似题目：

Distinct Prime Factors of Product of Array

参考资料：

https://leetcode.com/problems/closest-divisors

https://leetcode.com/problems/closest-divisors/solutions/517595/java-c-python-easy-and-concise/

LeetCode All in One 题目讲解汇总(持续更新中...)