题目描述

给定一个整数，请判断它是否是3的次幂。

进一步： 能否不使用递归和循环？

样例1

输入：27
输出：true

样例2

输入：0
输出：false

样例3

输入：9
输出：true

样例4

输入：45
输出：false

算法

(数论) $O(1)$

判断 $n$ 是否是3的次幂，即判断 $n$ 的质因子是否只有3。

整型范围内3的最大次幂是 $3^{19} = 1162261467$。则 $n$ 的质因子只有3，就等价于 $n$ 能整除 $1162261467$。

时间复杂度分析：只有一次取模运算，时间复杂度是 $O(1)$。

C++ 代码

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