leetcode解題：(Easy) 326. Power of Three

題目：https://leetcode.com/problems/power-of-three/description/

描述：判斷輸入的數字是否為3的次方數

解題思路(1)：用對數的基底變換計算

，如果i = log10(n) / log10(3)的i為整數的話代表n為3的次方數

程式碼：

class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && (Math.log10(n) / Math.log10(3)) % 1 == 0;
    }
}

時間複雜度：O(1)
空間複雜度：O(1)

---

解題思路(2)：如果要找的基底是質數的話還能用另一個技巧，因為質數只能被質數本身和1整除，所以我們可以找出題目輸入的限制中(這題中輸入最大到2^31 - 1)最大的3的次方數(在這題中會是3^19)，如果輸入n能被3^19整除則代表n也是3的次方數

程式碼：

class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && Math.pow(3, 19) % n == 0;
    }
}

時間複雜度：O(1)
空間複雜度：O(1)

tags: leetcode easy math method