326.Power of Three

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：
字数统计: 335 | 阅读时间 ≈ 1

题目描述

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

Example 1:
Input: 27
Output: true

Example 2:
Input: 0
Output: false

Example 3:
Input: 9
Output: true

Example 4:
Input: 45
Output: false

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

我的解法

解题思路

求一个数是不是3的幂，想到的方法是将一个数不断的求模并且将n除以3，如果模不等于零就停止，判断n是不是等于1，如果不等于1那就不是3的幂。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isPowerOfThree(int n) {
        if (n <= 0) return false;
        if (n == 1) return true;
        int mod = 0;
        while (mod == 0){
            mod = n % 3;
            n /= 3;
        }
        if (n == 0 && mod == 1)
            return true;
        else
            return false;
    }
};

Runtime: 16 ms, faster than 67.53% of C++ online submissions for Power of Three.
Memory Usage: 8.1 MB, less than 90.48% of C++ online submissions for Power of Three.

题目中还要求程序中不使用循环或者递归

高票解法

主要有两种方法

1
2
3
4
5
6
7
8
9
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;
    }
};

利用int的上限，求最大的3的幂，它除以n的模为零就说明n是3的幂

1
2
3
4
5
6
7
8
class Solution {
public:
    bool isPowerOfThree(int n) {
        if(n == 0) return false;
        double x = log10(n) / log10(3);
        return floor(x) == x;
    }
};

通过换底公式来判断。