Power of Four

Question

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?

Tags

• Mathematics
• Bit

Thought

Two solutions:

• Use logarithmic value like previous problem.
• Use binary number

For the first solution, the implementation is below and easy to understand.

For the second solution, we can find the pattern for all the power of four in binary number like Power of Two:

1  -> 0b0000001
4  -> 0b0000100
16 -> 0b0010000
64 -> 0b1000000

Patterns are below:

1. There should be only exactly one 1 in the binary number
2. The index of the 1 in the binary number should be always even number if we count from the right side.

Code

Use logarithmic value

class Solution(object):
    def isPowerOfFour(self, num):
        """
        :type num: int
        :rtype: bool
        """
        return num > 0 and 4 ** round(math.log(num,4)) == num

Use binary number

class Solution(object):
    def isPowerOfFour(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if num <= 0:
            return False
        binaryNum = bin(num)
        binaryList = list(binaryNum)
        binaryList.reverse()
        index = binaryList.index('1')
        return index % 2 == 0 and binaryNum.count('1') == 1