题目

给定一个整数，写一个函数来判断它是否是 3 的幂次方。

示例 1:

1 2	输入: 27 输出: true

示例 2:

1 2	输入: 0 输出: false

示例 3:

1 2	输入: 9 输出: true

示例 4:

1 2	输入: 45 输出: false

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

Given an integer, write a function to determine if it is a power of three.

Example 1:

1 2	Input: 27 Output: true

Example 2:

1 2	Input: 0 Output: false

Example 3:

1 2	Input: 9 Output: true

Example 4:

1 2	Input: 45 Output: false

Follow up:
Could you do it without using any loop / recursion?

解题方法

递归

试试递归，先确定递归推出条件，取小于3的值，1返回True，其余返回False；对于大于等于3的值，不能被3整除也返回False，能被3整除的进行递归。

class Solution {
    public boolean recursion(int n){
        if (n <= 0 || n == 2) {
            return false;
        }
        else if(n == 1) {
            return true;
        }
        else if(n % 3 != 0) { 
            return false;
        }
        else{
            return recursion(n / 3);
        }
    }
    
    public boolean isPowerOfThree(int n) {
        return recursion(n);
    }
}

代码可以简化一下，小于0直接返回False，大于0判断是否能被3整除，能就进行递归，否则判断是否等于1。这段代码跑了84ms，超过了64.07%的Java提交。

class Solution {
    // Method1 84ms 64.07%
    public boolean recursion(int n){
        if (n <= 0) {
            return false;
        }
        else if(n % 3 == 0) { 
            return recursion(n / 3);
        }
        else{
            return n == 1;
        }
    }
    
    public boolean isPowerOfThree(int n) {
        return recursion(n);
    }
}

循环

把递归改写为循环，这里的转化十分简单，递归调用改为循环判断是否能被3整除就好了，这段代码跑了15ms，超过了95.47%的Java提交。

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

数论

观察一下，假设一个素数$a$，那么$a$的幂均为$X=a^n$，其中$n>=0$，$X$的因子只有一个数$a$，则能整除$X$的非负整数只有$a^m$，其中$0<m\leq n$，均为$a$的幂，负数肯定不会是$a$的幂；对于一个非素数$b$，假设$b=i*j$，那么它的幂均为$Y=(ij)^n$，其中$n\geq0$，$Y$的因子有$i$和$j$两个，则能整除$Y$的是这样的数$Z=i^pj^q$，其中$0<p\leq n,0<q\leq n$，当$p$不一定等于$q$时，所以$Z$不一定为$b$的幂。

所以对于3，它是个素数，我们只需要判断参数n是否能整除int型范围内最大的3的幂1162261467。这段代码跑了13ms，超过了100%的Java提交。

class Solution {
    // Method3 13ms 100%
    public boolean isPowerOfThree(int n){
        return n > 0 && 1162261467 % n == 0;
    }
}