Power of Three

https://leetcode.com/problems/power-of-three/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?

Thoughts

如果是3的power, 那么能一直/3一直到 1且每次除后的数和3取余都为0.

Code

class Solution {
    public boolean isPowerOfThree(int n) {
        while (n > 1) {
            if (n % 3 != 0) {
                return false;
            }
            n = n / 3;
        }

        return n == 1 ? true : false;
    }
}

Analysis

时间复杂度是O(lgn).

Ver.2

我们可以找到MaxPow(3)最大能取到的数, 给定的N如果是3的倍数, 那么MaxPow(3) % N == 0.

class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}