0326. Power of Three

题目信息

题号:

0326

难度:

Easy

主题:

整数、幂、指数、正数边界

原题:

LeetCode 0326

重点:

指数必须是整数、3^0 等于 1、零和负数都不是三的幂

题目重述

给定 32 位有符号整数 n,判断是否存在整数 x 使 n = 3^x。由于结果需要是整数且三的整数次幂为正数,只有正整数可能满足条件。

n 位于 [-2^31, 2^31-1]。指数 x 可以为 0,所以 1 = 3^0 应返回 true;0、负数以及含有其他质因子的正整数都应返回 false。进阶问题询问能否不使用循环或递归完成判断。

自建示例

较高次幂:

输入:n = 81
输出:true
解释:81 = 3^4,因此存在整数指数满足条件。

零不是三的幂:

输入:n = 0
输出:false
解释:任意整数指数下的 3 的幂都不会等于 0。

指数为零:

输入:n = 1
输出:true
解释:1 = 3^0。

反复除以 3 验证质因子

正数 n 若是 3 的幂,连续除以 3 后一定恰好得到 1;过程中只要出现不能整除 3 的余数,就说明还含有其他质因子,不能再成为三的幂。先排除非正数,n == 1 会自然地在循环前通过。

这里不使用对数判断,因为浮点对数在整数幂附近可能有舍入误差;除法循环直接操作整数,也清楚地覆盖 3^0 的边界。

C++ 实现

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

代码分析

每次循环都去掉一个 3 因子;如果原数是 3^x,最终只剩 1,如果不是,剩余数会大于 1。循环次数为 O(log_3 n),额外空间为 O(1)。这没有采用题目进阶中“不使用循环”的常数技巧,但避免了把一个未解释的最大幂常量当作结论。