342.Power of Four

Tags: [math], [bit_manipulation]

Link: https://leetcode.com/problems/power-of-four/\#/description

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example:
Given num = 16, return true. Given num = 5, return false.

Follow up: Could you solve it without loops/recursion?

Credits:
Special thanks to@yukuairoyfor adding this problem and creating all test cases.

Solution: Bit manipulation

class Solution(object):
    def isPowerOfFour(self, num):
        """
        :type num: int
        :rtype: bool
        """
        return num > 0 and (num & (num - 1) == 0) and (num & 0x55555555 == num)

Revelation:

• Power of four, is the number such as, 4^0, 4^1, 4^2, 4^3, ...
• First the number is power of 4, this number must be the power of 2. The power of 2 means in the binary form, there is only '1', all other bits are '0', so we can use num & (num - 1) == 0 to check whether the num is power of 2 or not.
• 4^0 => binary(0001), 4^1 => binary(0100), 4^2 => binary(00010000), we can recognize that the bit '1' must on the odd position, cannot be on the even position. So we use num & 0x55555555 == 0 to check whether all '1's on the odd position.
• Why we use 0x55555555 to check all '1's on the odd position, because 5 = binary(0101), so 0x55555555 = binary(...01010101), if num's all '1's on the odd position, the num & 0x55555555 should be equal to num itself.

Note:

• Time complexity = O(1).

Solution: Loop

class Solution(object):
    def isPowerOfFour(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if num < 0:
            return False

        exp = 0
        while 4 ** exp <= num:
            if 4 ** exp == num:
                return True
            exp += 1

        return False

Note:

• Time complexity = O(log(num), log_base = 4). Because 4^k = num, k = log(num), log_base = 4. k starts from 0, and each time increased by 1, so if k want to increase to log(num), log_base = 4, it will take log(num) - 1 times iterations (log_base = 4). So the time complexity = O(log(num), log_base = 4).