326. 3 的幂
题目描述
输入一个整数 n。
如果存在整数 x，使得 n == 3^x，那么 n 就是 3 的幂。是 3 的幂时返回 true，否则返回 false。注意 1 = 3^0 也算，0 和负数都不算。
示例 1
输入：n = 27 输出：true
解释：27 = 3^3。
示例 2
输入：n = 0 输出：false
解释：0 不是 3 的任何整数次幂。
示例 3
输入：n = -1 输出：false
解释：负数不可能是 3 的幂。
数据范围
-2^31 <= n <= 2^31 - 1
进阶：能否不用循环和递归完成？
解题思路：试除
3 的幂只含质因子 3。只要 n 能被 3 整除就不断除以 3，把所有因子 3 剥掉。剥完之后若剩下 1，说明除了 3 没有别的因子；剩下别的数，说明还混有其他质因子。非正数先直接排除，否则 0 会让循环永远停不下来。
为什么正确
每次除以 3 之前 n 能被 3 整除，所以“原数是 3 的幂”与“当前 n 是 3 的幂”始终等价。
复杂度分析
时间 O(log n)，最多除约 20 次；额外空间 O(1)。
易错点
忘记先排除 n <= 0：n = 0 时 0 % 3 == 0 永远成立，循环会死循环。负数也不可能是 3 的幂。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def isPowerOfThree(self, n: int) -> bool:
if n <= 0:
return False
while n % 3 == 0:
n //= 3
return n == 1class Solution {
public boolean isPowerOfThree(int n) {
if (n <= 0) {
return false;
}
while (n % 3 == 0) {
n /= 3;
}
return n == 1;
}
}class Solution {
public:
bool isPowerOfThree(int n) {
if (n <= 0) {
return false;
}
while (n % 3 == 0) {
n /= 3;
}
return n == 1;
}
};func isPowerOfThree(n int) bool {
if n <= 0 {
return false
}
for n%3 == 0 {
n /= 3
}
return n == 1
}var isPowerOfThree = function(n) {
if (n <= 0) {
return false;
}
while (n % 3 === 0) {
n /= 3;
}
return n === 1;
};function isPowerOfThree(n: number): boolean {
if (n <= 0) {
return false;
}
while (n % 3 === 0) {
n /= 3;
}
return n === 1;
}其他解法
试除法不断除以 3 看是否剩 1，需要 O(log n)；约数判定利用 3 是质数，把问题转化为是否整除一个常数，O(1) 完成。
解法 2：判断是否为最大 3 的幂的约数 时间 O(1)，空间 O(1)
32 位有符号整数范围内最大的 3 的幂是 3^19 = 1162261467。因为 3 是质数，3^19 的约数只有 3^0 到 3^19。所以 n 是 3 的幂当且仅当 n > 0 且 1162261467 % n == 0。
不用循环，满足进阶要求。只对质数的幂成立，且依赖固定的整数范围。
class Solution:
def isPowerOfThree(self, n: int) -> bool:
return n > 0 and 1162261467 % n == 0class Solution {
public boolean isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}
}class Solution {
public:
bool isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}
};func isPowerOfThree(n int) bool {
return n > 0 && 1162261467%n == 0
}var isPowerOfThree = function(n) {
return n > 0 && 1162261467 % n === 0;
};function isPowerOfThree(n: number): boolean {
return n > 0 && 1162261467 % n === 0;
}