Solution 1 - Iterative Division

Given an integer n, return true if it is a power of four, otherwise return false. A power of four is a number of the form $4^k$ where k is a non-negative integer. Repeatedly divide n by 4 and check if we reach 1.

TimeComplexity: O(\log n)

SpaceComplexity: O(1)

""" 0342.1 - Power of Four - Solution 1 - Iterative Division """

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def isPowerOfFour(self, n: int) -> bool:
        """Power of Four Function"""
        if n <= 0:
            return False
        while n % 4 == 0:
            n //= 4
        return n == 1


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().isPowerOfFour(16))   # True
    print(Solution().isPowerOfFour(5))    # False
    print(Solution().isPowerOfFour(1))    # True
    print(Solution().isPowerOfFour(0))    # False
    print(Solution().isPowerOfFour(-4))   # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Bit Manipulation

A number is a power of four if it satisfies three conditions: it is positive, it is a power of two (only one bit set, checked via n & (n - 1) == 0), and that single set bit is at an even position (checked via n & 0x55555555 != 0, where 0x55555555 is a bitmask with 1s at all even bit positions).

TimeComplexity: O(1)

SpaceComplexity: O(1)

""" 0342.2 - Power of Four - Solution 2 - Bit Manipulation """

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def isPowerOfFour(self, n: int) -> bool:
        """Power of Four Function"""
        return n > 0 and (n & (n - 1)) == 0 and (n & 0x55555555) != 0


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().isPowerOfFour(16))   # True
    print(Solution().isPowerOfFour(5))    # False
    print(Solution().isPowerOfFour(1))    # True
    print(Solution().isPowerOfFour(8))    # False (power of 2, not 4)
    print(Solution().isPowerOfFour(64))   # True


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 3 - Math (Logarithm)

Use the mathematical property that if n is a power of four, then $\log_4(n)$ must be an integer. We compute this using log(n) / log(4) and check if the result is a whole number.

TimeComplexity: O(1)

SpaceComplexity: O(1)

""" 0342.3 - Power of Four - Solution 3 - Math (Logarithm) """

#####################################################################################
# Imports
#####################################################################################
import math

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def isPowerOfFour(self, n: int) -> bool:
        """Power of Four Function"""
        if n <= 0:
            return False
        return math.log2(n) % 2 == 0


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().isPowerOfFour(16))   # True
    print(Solution().isPowerOfFour(5))    # False
    print(Solution().isPowerOfFour(1))    # True
    print(Solution().isPowerOfFour(64))   # True
    print(Solution().isPowerOfFour(32))   # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0342 - Power of Four

Solution 1 - Iterative Division

Solution 2 - Bit Manipulation

Solution 3 - Math (Logarithm)