Power of Two (231)

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

Approach 1:

We check if n can be divided by 2. If yes, divide n by 2 and check it repeatedly.

**Could also implement it recursively however less eficient due to space being used in the call stack

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

Complexity: O(log(N)time

Approach2 :

Very intuitive using bitcount. If n is the power of 2, the bit count of n is 1. Note that 0b1000...000 is -2147483648, which is not the power of two, but the bit count is 1.

return n > 0 && Integer.bitCount(n) == 1;

Time complexity = O(1) The time complexity of bitCount() can be done by a fixed number of operations. More info in https://stackoverflow.com/questions/109023.