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


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

Last Updated: 5/13/2020, 7:39:18 AM