Power of Three (326)

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

Approach 1:

the simplest way to find if a number n is a power of c is simply by continually dividing n by c as long as the remainder is 0.

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

Complexity: O(log2(N) time

Approach2 :

We can solve this one just by using math. if n = 3^x, then x = log(n) / log(3), and thus we come to the solution.

Here is the math:

log(n) / log(3) <==> log(3)^x / log(3) for n == 3 ^ x, and x is integer. Use log formula to bring x to front, we have x*log(3) / log(3), which is equal to x. We only need to check if x is an whole number by using x % 1 == 0.

class Solution {
    public boolean isPowerOfThree(int n) {
        double x = Math.log10(n) / Math.log10(3);
        return x % 1 == 0;
    }
    //log10 is used to avoid a precision erro from using log2
}

Complexity: O(N) time and O(1) space.