Easy
题目描述
给定一个整数 n，如果它是 3 的幂次，则返回 true；否则，返回 false。
如果存在整数 x 使得 n == 3^x，则认为 n 是 3 的幂次。
示例 1：
输入：n = 27
输出：true
解释：27 = 3^3
示例 2：
输入：n = 0
输出：false
解释：不存在 x 使得 3^x = 0
示例 3：
输入：n = -1
输出：false
解释：不存在 x 使得 3^x = -1
提示：
-2^31 <= n <= 2^31 - 1
进阶： 你能不使用循环或者递归来解决这个问题吗？
解题思路
这道题有多种解法，我们来分析几种主要思路：
方法一：循环除法 最直观的方法是不断将 n 除以 3，如果 n 能被 3 整除就继续，直到 n 变成 1（说明是 3 的幂）或者不能被 3 整除（说明不是 3 的幂）。需要注意 n 必须大于 0。
方法二：递归 递归思路与循环类似，基础情况是 n = 1 返回 true，n < 1 或不能被 3 整除返回 false，否则递归检查 n/3。
方法三：数学技巧（推荐） 这是最优雅的解法。由于题目给定了 n 的范围是 32 位整数，我们可以找到这个范围内最大的 3 的幂次，即 3^19 = 1162261467。如果 n 是 3 的幂次，那么最大的 3 的幂次一定能被 n 整除（因为 3 是质数）。
这种方法的时间复杂度是 O(1)，不使用循环或递归，完美符合进阶要求。首先检查 n > 0，然后检查 1162261467 % n == 0。
代码实现
class Solution {
public:
bool isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}
};
class Solution:
def isPowerOfThree(self, n: int) -> bool:
return n > 0 and 1162261467 % n == 0
public class Solution {
public bool IsPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}
}
var isPowerOfThree = function(n) {
return n > 0 && 1162261467 % n === 0;
};
复杂度分析
| 复杂度类型 | 数学方法 | 循环方法 |
|---|---|---|
| 时间复杂度 | O(1) | O(log₃n) |
| 空间复杂度 | O(1) | O(1) |
相关题目
. Power of Two (Easy)
. Power of Four (Easy)