原文链接: https://leetcode-cn.com/problems/power-of-three

英文原文

Given an integer n, return true if it is a power of three. Otherwise, return false.

An integer n is a power of three, if there exists an integer x such that n == 3x.

 

Example 1:

Input: n = 27
Output: true

Example 2:

Input: n = 0
Output: false

Example 3:

Input: n = 9
Output: true

Example 4:

Input: n = 45
Output: false

 

Constraints:

• -231 <= n <= 231 - 1

 

Follow up: Could you solve it without loops/recursion?

中文题目

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x

 

示例 1：

输入：n = 27
输出：true

示例 2：

输入：n = 0
输出：false

示例 3：

输入：n = 9
输出：true

示例 4：

输入：n = 45
输出：false

 

提示：

• -231 <= n <= 231 - 1

 

进阶：

• 你能不使用循环或者递归来完成本题吗？

通过代码

高赞题解

数学

一个不能再朴素的做法是将 $n$ 对 $3$ 进行试除，直到 $n$ 不再与 $3$ 呈倍数关系，最后判断 $n$ 是否为 $3^0 = 1$ 即可。

代码：

class Solution {
    public boolean isPowerOfThree(int n) {
        if (n <= 0) return false;
        while (n % 3 == 0) n /= 3;
        return n == 1;
    }
}

• 时间复杂度：$O(\log_{3}n)$
• 空间复杂度：$O(1)$

---

倍数 & 约数

题目要求不能使用循环或递归来做，而传参 $n$ 的数据类型为 int，这引导我们首先分析出 int 范围内的最大 $3$ 次幂是多少，约为 $3^{19} = 1162261467$。

如果 $n$ 为 $3$ 的幂的话，那么必然满足 $n * 3^k = 1162261467$，即 $n$ 与 $1162261467$ 存在倍数关系。

因此，我们只需要判断 $n$ 是否为 $1162261467$ 的约数即可。

注意：这并不是快速判断 $x$ 的幂的通用做法，当且仅当 $x$ 为质数可用。

代码：

[]
class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

---

打表

另外一个更容易想到的「不使用循环/递归」的做法是进行打表预处理。

使用 static 代码块，预处理出不超过 int 数据范围的所有 $3$ 的幂，这样我们在跑测试样例时，就不需要使用「循环/递归」来实现逻辑，可直接 $O(1)$ 查表返回。

代码：

[]
class Solution {
    static Set<Integer> set = new HashSet<>();
    static {
        int cur = 1;
        set.add(cur);
        while (cur <= Integer.MAX_VALUE / 3) {
            cur *= 3;
            set.add(cur);
        }
    }
    public boolean isPowerOfThree(int n) {
        return n > 0 && set.contains(n);
    }
}

• 时间复杂度：将打表逻辑交给 $OJ$ 执行的话，复杂度为 $O(\log_3{C})$，$C$ 固定为 $2147483647$；将打表逻辑放到本地执行，复杂度为 $O(1)$
• 空间复杂度：$O(\log_3{n})$

---

其他「$x$ 的幂」问题

题目简单？不如来看「矩阵快速幂」三部曲 🍭🍭🍭：

题目	题解	难度	推荐指数
1137. 第 N 个泰波那契数	LeetCode 题解链接	简单	🤩🤩🤩🤩🤩
剑指 Offer 10- I. 斐波那契数列	LeetCode 题解链接	简单	🤩🤩🤩🤩🤩
552. 学生出勤记录 II	LeetCode 题解链接	困难	🤩🤩🤩🤩

或是加练如下的「$x$ 的幂」问题 🍭🍭🍭：

题目	题解	难度	推荐指数
231. 2 的幂	LeetCode 题解链接	简单	🤩🤩🤩🤩
342. 4的幂	LeetCode 题解链接	简单	🤩🤩🤩🤩

---

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

统计信息

通过次数	提交次数	AC比率
142288	281938	50.5%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
2 的幂	简单
4的幂	简单