LeetCode 326 Power of Three

    
        标签：
        
            数学类题目
        
            LeetCode
        
    发布于：2022-03-07 16:21:42
    编辑于：2022-03-07 16:30:14
    浏览量：719

概述

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);
}

Links: leetcode-326-power-of-three