[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 題目講解匯總(持續更新中...)