LeetCode OJ: 326. Power of Three 三次方判斷

此題 LeetCode 提供了四種解法：Loop Iteration、Base Conversion、Mathematics、Integer Limitations。

方法一： Loop Iteration
一個整數是 3 的某次方時(3^x)，可以寫成如下表示方式：
n = 3 ^ x
n = 3 * 3 * 3 * 3 … * 3
也就是將 n 除以 3 做 x 次後，會得到整數 1 。於是可以用迴圈一直除以 3，直到餘數不是零。最後在判斷有沒有得到整數 1。

C++ 程式碼：

class Solution {
public:
    bool isPowerOfThree(int n) {
        if(n < 1)   return false;
        
        while(n % 3 == 0)   n /= 3;
        
        return n == 1;
    }
};

方法二： Base Conversion
十進制時，10 ^ 0 = 1；10 ^ 1 = 10；10 ^ 2 = 100 … etc。只要是 10 ^ x 次方時，一定會是以 1 開頭，接著連續 0 的形式出現： 。

那二進制時呢？ 2 ^ 0 = 1； 2 ^ 1 = 10；2 ^ 2 = 100 … etc。也是 形式。所以可以將數字 n 轉換成 三進制 的字串，在 檢查數字 1 是否只有出現一次 。

C++ 程式碼：

class Solution {
public:
    bool isPowerOfThree(int n) {
        string s = "";
        char c;

        // convert n into base 3 as string
        while(n / 3 > 0)
        {
            c = (n%3) + '0';
            s.append(string(1, c));
            n = n / 3;
        }

        // the last digit
        c = n + '0';
        s.append(string(1, c));
        
        // Check checking if the string contains only one 1.
        int cnt = 0;
        for(int i = s.length() - 1; i >= 0; i--)
        {
            if(s[i] == '2')
            {
                cnt += 2;
                break;
            }
            else if(s[i] == '1')
            {
                cnt++;
                if(cnt > 1)
                {
                    break;
                }
            }
        }

        return cnt == 1;
    }
};

方法三： Mathematics
若 n 為 3 的 x 次方，那麼以 3 為底，對 n 取對數會得到整數的結果。而C++ math 所提供的對數函數沒有以 3 為底。但可以使用換底公式(下圖取自 Wikipedia)：

以十為底來計算。接著使用 floor() 函數來判斷計算結果是不是一個整數。

C++程式碼：

class Solution {
public:
    bool isPowerOfThree(int n) {
        double r = (log10(n) / log10(3));
        int fr = floor(r);
        return fr == r;
    }
};

方法四： Integer Limitations
在程式語言中，整數會有最大值的限制，C++ 中可以使用 INT_MAX 來查詢到最大值為 2147483647。那麼找出小於 INT_MAX 的 3 ^ x 次方之數值，這個數值會是 3 ^ 19 = 1162261467 。而其他的 3 ^ x 一定會是 3 ^ 19 的因數，所以就可以用求餘數的方式來判斷了。

C++ 程式碼：

class Solution {
public:
    bool isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
};

而針對這四種方法，LeetCode在解答部分有做了 Java 程式碼執行速度的比較：

可以看出第四種方法是最快的。依上面的解法，讀者可以試著解這題： https://leetcode.com/problems/power-of-four/

Originally published at https://yunlinsong.blogspot.com.