# Problem

problem at: https://leetcode.com/problems/power-of-four

# Solution

# Vanilla Iteration

Could also do in recursion instead of while loop but omitted.

We could either increase or decrease w/ time and constant space.

# Increase

We could increase acc till it's equal to or larger than n.

def isPowerOfFour(self, n: int) -> bool:
    if n<1: return False
    elif n==1: return True
    acc = 1
    while acc < n:
        acc *= 4
        if acc==n:
            return True
    return False

# Decrease

We could decrease n till it's equal to or smaller than 1.

def isPowerOfFour(self, n: int) -> bool:
    if n<1: return False
    while n>1:
        n /= 2
    return n==1

# Follow Up

Could you solve it without loops/recursion?

# Math

If n is a power of 4: , then . So we simply check if is even.

Complexity:

  • time:
  • space:
def isPowerOfFour(self, n: int) -> bool:
    return n > 0 and math.log2(n) % 2 == 0

# Bit Manipulation

First check if n is a power of 2 (necessary condition). Further, n would have 1 at an even position, such as 0001 or 0100. So n & 1010...10 would yield a 0. Note that 32-bit 1010...10 would be aaaaaaaa in hex.

Complexity:

  • time:
  • space:
def isPowerOfFour(self, n: int) -> bool:
    return n > 0 and n & (n-1) == 0 and n & 0xaaaaaaaa == 0

or instead of 0xaaaaaaaa, n & 0x55555555 would be non-zero:

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

# Modular Arithmatic

Also check if n is a power of 2.

consider both cases and , and to compute modulo after division by 3:

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

# Integer Limitation

In __init__ method calculate all powers of 4 smaller than .

class Solution:
    def __init__(self):
        max_int = 2**31-1
        self.powerOfFour = [1,4]
        while self.powerOfFour[-1] < max_int/4:
            self.powerOfFour.append(self.powerOfFour[-1]*4)

    def isPowerOfFour(self, n: int) -> bool:
        return n>0 and n in self.powerOfFour