LeetCode - 507. Perfect Number

tags: LeetCode Guide C++ Easy

原題連結: https://leetcode.com/problems/perfect-number/

Difficulty: Easy

題目說明

We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself.

Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not.

範例測資

Example 1.

Input:

28

Output:

True

Explanation:

28 = 1 + 2 + 4 + 7 + 14

Note:

The input number **n** will not exceed 100,000,000. (1e8)

說明

這題其實還蠻尷尬的，實際上不太像是在考你code，偏向數學的成分居多。
總之就是要檢查完全數，完全數就是把這個數本身的因數(不包含自己)全部相加，最後得到的總和會正好等於自己。

例如: 6的因數有1、2、3、6，因為不包含自己，所以只計算1+2+3，得到6自己，所以6就是一個完全數。

題目會給一個數字，試著檢查它是不是完全數。

Code與解析

作法1. Brute Force [Accept] [TimeLimitExceed]

Runtime: 1180 ms > faster than 26.76%
Memory: 8 MB > less than 100.00%

class Solution {
public:
    bool checkPerfectNumber(int num) {
        if(num <= 1) return false;
        int sum = 1;
        for(int i = 2; i <= num / 2; i++){
            if(num % i == 0) sum += i;
        }
        return sum == num;
    }
};

作法1是最為直觀的暴力破解，從1開始到num的一半為止(剩下的一定不是因數)全部檢查一遍，最後檢查因數總和。然而，當num本身足夠大的時候，要計算比對的次數就會激增，從而導致TLE，顯然有其他方法。

p.s. 2020/01/03 重新上傳一次code，可以得到AC，可能把時限放寬了，但理論上應該要TLE。

作法2. Optimal Solution [Accept]

Runtime: 0 ms > faster than 100.00%
Memory: 8 MB > less than 100.00%

class Solution {
public:
    bool checkPerfectNumber(int num) {
        if(num <= 1) return false;
        int sum = 1, i = 2;
        for(i = 2; i * i < num; i++){
            if(num % i == 0) {
                sum += i;
                sum += num / i;
            }
        }
        if(i * i == num) sum += i;
        return sum == num;
    }
};

與作法1不同的是，作法2的迴圈的範圍限制在了i * i < num。
理由是這樣的，因為我們今天所找的是因數，基本上，因數必定是成對出現的，只有一個情況除外:i * i = num的i本身。
因此如果我們確定i是因數，那num/i也一定是因數，並且只要檢查到

$\sqrt{num}$即可