LeetCode 326 Power of Three

概述

https://leetcode.com/problems/power-of-three/

递归法

时间复杂度 O(logn)。

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

质数法

https://leetcode.com/problems/power-of-three/discuss/77856/1-line-java-solution-without-loop-recursion

利用其质数的性质，

public class Solution {
public boolean isPowerOfThree(int n) {
    // 1162261467 is 3^19,  3^20 is bigger than int  
    return ( n > 0 &&  1162261467 % n==0);
}