326. Power of Three

1. 问题描述

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?
Tags: Math
Similar Problems: (E) Power of Two (E) Power of Four

2. 解题思路

判断一个数是否为3的次方数，且不能使用循环或递归，即要求时间和空间复杂度都为常数！

思路1：不停地除以3，判断最后的余数是否为1。注意：需考虑输入是负数和0的情况！
思路2：利用对数的换底公式来做，换底公式为log_ab = log_cb / log_ca，那么如果n是3的倍数，则log₃n一定是整数，我们利用换底公式可以写为log₃n = log₁₀n / log₁₀3，注意这里一定要用10为底数，不能用自然数或者2为底数，否则当n=243时会出错，原因请看这个帖子。现在问题就变成了判断log₁₀n / log₁₀3是否为整数，在c++中判断数字a是否为整数，我们可以用 a - int(a) == 0 来判断。
思路3：由于输入是int，正数范围是0-2³¹，在此范围中允许的最大的3的次方数为3¹⁹=1162261467，那么只要看这个数能否被n整除即可。

3. 代码

思路1

1 class Solution {
2 public:
3     bool isPowerOfThree(int n) {
4         while (n && n % 3 == 0) {
5             n /= 3;
6         }
7         return n == 1;
8     }
9 };

思路2

 1 class Solution {
 2 public:
 3     bool isPowerOfThree(int n) {
 4         if(n==0)
 5             return false;
 6         if ((math.log10(n) / (math.log10(3))) - (int) ((math.log10(n) / (math.log10(3)))) ==0) 
 7         {
 8             return true;
 9         }
10         return false;
11     }
12 };

思路3

1 class Solution {
2     public:
3         bool isPowerOfThree(int n) {
4             return (n > 0 && 1162261467 % n == 0);
5         }
6     };

326. Power of Three

1. 问题描述

2. 解题思路

3. 代码

4. 反思