LeetCode #507 Perfect Number 解題思路及翻譯

LeetCode題目翻譯

英文原文如下

A perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. A divisor of an integer x is an integer that can divide x evenly.

Given an integer n, return true if n is a perfect number, otherwise return false.

中文翻譯

「完全數」是一個正整數，其數字剛好會等於他的因數(正整數)加總，因數不含自己本身。

因數定義 : 一個可以完整整除 整數x 的數字

給予一個整數n，回傳n是否為完全數

num的數字介於 1 到 10⁸之間

以下是官方提供的範例

來看下例子1的 28吧，因數共有 1,2,4,7,14 ➔ 28本身不算

1 + 2 + 4 + 7 +14 = 28成立，故回傳true

例子2 的 7 (我覺得官方這裡寫得很有問題，完全沒有解釋)

7為質數，但1 應該也要被算為因數(如上例)

1 != 7，故回傳false

解題思路

C# 解決方案

方案1 – 直接遞迴，效能低落

看到因數的題目，相信大家都會想到直接從1開始直接計算是否為因數就好(餘數為0)

那我們來實作看看

public class Solution {
    public bool CheckPerfectNumber(int num) {
        if(num == 1)      //數字本身不能當作因數
        {
            return false;
        }
        
        int sum = 0;
        
        for(int i =1; i<num;i++)
        {
            if(num%i ==0)           //餘數為0，即為因數
            {
                sum+=i;
            }
        }
        
        return num == sum;
    }
}

看起來確實挺簡單的，一路從 1 跑到 num-1的地方，要是有就加入sum

測試範例執行起來也都沒有問題，那我們提交看看

天啊!居然跑得超過時間限制了

看了看數字 : 99999997 ，總共幾個9我都數不清了

方案2 – 修正版 ➡ 跑到根號 num 就好

這時讓我們倒退一下，回來思考一下概念

一個數字 x 要是有因數，一定可以寫成 a * b ➔ 因數 * 另一個數

就題目看來 1 也算的話，應該任意正整數都能寫成 a * b

這時候我們來想一下如何找到距離最近的a 跟 b呢

直接 x 除2嗎 ?

以 36 為例 ➔ 因數可得到 : 1、2、3、4、6、9、12、18

1 跟 36 ➔ 差為 35，36 甚至不能算在因數裡

2 跟 18 ➔ 差為 16

…

6 跟 6 ➔ 差為 0

省略列出每一個，大家可以得到 6

以此類推，大家應該可以得到任意數 x 距離最近的因數 a 跟 b ，就會是 x^1/2 ，也就是根號 x

這時，大家疑惑的點可能變成，這個數字可以做什麼呢?

大家這時來想想

要是 a 小於等於 根號 x ， b是不是就一定會大於等於 根號 x 呢?

好像是的吧?

那這時候要是我們的遞迴只跑到 根號 x 如何

反正我們能得到 a的時候，也可以用 x / a 得到 對應的 b

事不遲疑，我們把遞迴的限制改一下

public class Solution {
    public bool CheckPerfectNumber(int num) {
        if(num == 1)      
        {
            return false;
        }
        
        int sum = 1;
        //int max = (int)Math.Sqrt(num);   //上下兩句都是取根號的方法，開心用哪個都可以
        int max = (int)Math.Pow(num,0.5);
        
        for(int i =2; i<=max;i++)
        {
            if(num%i ==0)
            {
                sum+= i + num/i;       //文中提到的 a 跟 b
            }
        }
        return num == sum;
    }
}

程式碼幾乎相同，只有改了兩個小地方

• i 的Limit (本來要跑到 num-1，現在只要跑到 num^1/2 )
• 加總的多加了 【num ÷ i】

這時我們提交看看改過的程式

可以看到運行時間還算不錯，超過了7成左右的C# 提交

Java解決方案

方案1 – 遞迴跑到根號 num 就好

class Solution {
    public boolean checkPerfectNumber(int num) {
        if(num == 1)      
        {
            return false;
        }
        
        int sum = 1;
        //int max = (int)Math.sqrt(num);   //上下兩句都是取根號的方法，開心用哪個都可以
        int max = (int)Math.pow(num,0.5);
        
        for(int i =2; i<=max;i++)
        {
            if(num%i ==0)
            {
                sum+= i + num/i;       
            }
        }
        return num == sum;
    }
}

Python3 解決方案

方案1 – 遞迴跑到根號 num 就好

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num == 1:
            return False
        
        sum = 1;
        #max = math.ceil(math.sqrt(num)) #上下兩句都是取根號的方法，開心用哪個都可以
        max = math.ceil(num**0.5)
        
        for i in range(2,max):
            if num%i ==0:
                sum+= i + num/i
                
        return num == sum

JavaScript 解決方案

方案1

/**
 * @param {number} num
 * @return {boolean}
 */
var checkPerfectNumber = function(num) {
        if(num == 1)      
        {
            return false;
        }
        
        var sum = 1;
        //var max = parseInt(Math.sqrt(num));   //上下兩句都是取根號的方法，開心用哪個都可以
        var max = parseInt(Math.pow(num,0.5));
        
        for(let i =2; i<=max;i++)
        {
            if(num%i ==0)
            {
                sum+= i + num/i;       
            }
        }
        return num == sum;
};

結論

這一題的兩個答案，相當明確的指出就算是相同的寫法，要是建立在不同的前提上會有多少的差別

故寫程式除了對程式本身的優化外，邏輯也是非常重要的

"If everything was perfect, you would never learn and you would never grow."
                                                                                                                                                   Beyonce Knowles                           

( 如果所有事情都是完美的，你永遠不會學習也永遠不會成長 )

題目連結 : Perfect Number – LeetCode

圖片來源 : 封面 – 維基百科

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

最新文章

• LeetCode #2073 Time Needed to Buy Tickets 買到票所需要的時間2024-04-17
• Java 比較字串或字元是否相等(忽略大小寫)2024-04-16
• C# 比較字串或字元是否相等(忽略大小寫)2024-04-12
• LeetCode #1700 Number of Students Unable to Eat Lunch 吃不到午餐的學生數量2024-04-10
• LeetCode #1544 Make The String Great 讓字串變好2024-04-08