342. Power of Four - Explanation

1. Recursion

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        if n == 1:
            return True
        if n <= 0 or n % 4:
            return False
        return self.isPowerOfFour(n // 4)

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

2. Iteration

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        if n < 0:
            return False

        while n > 1:
            if n % 4:
                return False
            n //= 4

        return n == 1

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

3. Math

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        return n > 0 and log(n, 4) % 1 == 0

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

4. Bit Manipulation

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        if n < 0:
            return False

        for i in range(0, 32, 2):
            if n == (1 << i):
                return True

        return False

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

5. Bit Mask - I

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0 and (n & 0x55555555) == n

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

6. Bit Mask - II

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0 and (n % 3 == 1)

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$