描述 Description

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

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

[Power of Three]

分析 Analysis

方法1

通用方法。lz推荐

由于输入是int，正数范围是0-231，在此范围中允许的最大的3的次方数为maxPowerOfThree = 319=1162261467，那么我们只要看这个数能否被n整除即可；

方法2

通用方法。利用对数公式。把该整数对3取对数，如果结果是整数，说明该整数是3的幂。

Note: 对数感觉应该是用数值方法计算出来的，最慢。

方法3

通用方法。最简单的方法，不断除以3，看最后能否得到1。

小编觉得没有什么特殊的快速方法，直接是使用power of two中的通用方法。

代码 Code

方法1

class Solution {
public:
    int const Max3PowerInt = 1162261467; // 3^19, 3^20 = 3486784401 > MaxInt32
    int const MaxInt32 = 2147483647; // 2^31 - 1
    bool isPowerOfThree(int n) {
        if (n <= 0 || n > Max3PowerInt) return false;
        return Max3PowerInt % n == 0;
    }
};