题目

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

整数 是 的幂次方需满足：存在整数 使得

示例 1：

• 输入： n = 27
• 输出： true

示例 2：

• 输入： n = 0
• 输出： false

示例 3：

• 输入： n = 9
• 输出： true

示例 4：

• 输入： n = 45
• 输出： false

提示：

• 

方法一：试除法

思路及解法

我们不断地将 除以 ，直到 。如果此过程中 无法被 整除，就说明 不是 的幂。

本题中的 可以为负数或 ，可以直接提前判断该情况并返回 ，也可以进行试除，因为负数或 也无法通过多次除以 得到 。

代码

class Solution {
    func isPowerOfThree(_ n: Int) -> Bool {
        if n <= 0 {
            return false
        }

        var n = n
        while n % 3 == 0 {
            n /= 3
        }

        return n == 1
    }
}

复杂度分析

• 时间复杂度：。当 是 的幂时，需要除以 的次数为 ；当 不是 的幂时，需要除以 的次数小于该值。

• 空间复杂度：。

方法二：判断是否为最大 3 的幂的约数

思路及解法

我们还可以使用一种较为取巧的做法。

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

如果 为 的幂的话，那么必然满足 ，即 与 存在倍数关系。

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

与方法一不同的是，这里需要特殊判断 是负数或 的情况。

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

代码

class Solution {
    func isPowerOfThree(_ n: Int) -> Bool {
        return n > 0 && 1162261467 % n == 0
    }
}

复杂度分析

• 时间复杂度：。

• 空间复杂度：。