power-of-three

Power of Three – LeetCode 326

Problem

Description

Given an integer, write a function to determine if it is a power of three.

Answer

Original

Code

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

思路

最简单的方法，循环除3进行判断，时间复杂度$O(log_{3}{n})$，空间复杂度$O(1)$。
耗时$83$ ms，排名$91.05\%$

Better

思路

已知int的表示范围，直接生成容纳范围内的因数只有3 的最大值，符合要求的书与之取模结果应该是0。时间复杂度$O(1)$，空间复杂度$O(1)$。
耗时$76$ ms，排名$84.37\%$

Code

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