给定一个整数，写一个函数来判断它是否是 3 的幂次方。
示例 1:
输入: 27
输出: true
示例 2:
输入: 0
输出: false
示例 3:
输入: 9
输出: true
示例 4:
输入: 45
输出: false
进阶：
你能不使用循环或者递归来完成本题吗？
image
官方原题
见题知意，逻辑很清晰。
常规解法相信大家都可以想得到，即循环迭代。
分析：
n对x取余结果若为0，就一直将n整除x。直至n最终为1。若最终n不为1，则说明在某次执行n对x取余时结果不为0，换句话说n不是x的幂次方。
算法实现
复杂度分析：
时间复杂度：O(logn)，除数是用对数表示的。
空间复杂度：O(1)，没有使用额外的空间。
另外一种解法就不太容易想得到了，叫做整数限制。
由题目可以得出n的取值范围为整型数值的最大值，即2147483647，那么在此范围内的3的幂的最大值呢？
经计算可知：3的19次方是我们想要的值1162261467。
分析：
可知3的0至19次方均符合我们的题目要求，即返回true。另外由于3是质数，所以3的19次方的除数只有在为3的0次方、3的1次方……3的19次方的时候才可以整除，也即若3的19次方对n取余结果为0则说明n是3的0至19次方的一员，此时应返回true。
复杂度分析
时间复杂度：O(1)，我们只做了一次操作。
空间复杂度： O(1)，没有使用额外空间。
官方同时提供了基准转换和运算法两种高效算法，感兴趣的朋友可以深入研究下。
欢迎关注公众号“工程师修炼之道”，大量技术干货，面试技巧
网友评论