Is This A Power Of Four — Leetcode Challenge

https://unsplash.com/@eduardoequis

I thought for sure today was going to be a binary tree challenge. It wasn’t. Instead…

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

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

Example 1:
Input: 16
Output: true
Example 2:
Input: 5
Output: false

Here are two basic approaches with two variations each. All of them were accepted. I’ll run some benchmark timing and update this post with that.

Overview
A few things to note:

1. One (1) is a power of everything, so if num == 1 , it’s automaticallyTrue.
2. Negative numbers are outside the scope of the challenge, and two and three aren’t powers of 4. All of these get caught in the test for num < 4 , and return False.
3. String Slicing
   a: [x:y] means start at index x, and stop at index y, without including y.
   b: If x is absent, then it means from the beginning (0) to y, without including y.
   c: If y is absent, it means start from x and go to the end of the string.
   d: [::-1] is a way to reverse the item it’s associated with.

myStr = 'Oh wow, Monday again.'
print(myStr[3:6]) # prints out 'wow'
print(myStr[8:]) # prints out 'Monday again.'
print(myStr[:8]) # prints out 'Oh wow, ' (notice M is NOT included)
print(myStr[::-1] # prints out '.niaga yadnoM ,wow hO'

4. bin(num) returns a string containing a binary representation of num.

print(bin(32)) # '0b100000'
print(bin(64)) # '0b1000000'

Note that 32 is NOT a power of 4, but 64 is. There are 6 0s are the 1 in the binary representation of 64, but there are only 5 0s after the 1 in 32. I used this property to figure out if a number was a power of 4.

So, to summarize, the main if test in the solution looks for a 1 in index 2 (after the first 0b), then makes sure everything ELSE is a 0. After that, it checks to see if the length of the 0 part of the string is divisible evenly by 2. If all this is true? Winner! It’s a power of 4. Otherwise, nope, return False.

Solution 1: String Slicing

def isPowerOfFour(self, num):
  if num == 1:
    return True
  if num < 4:
    return False
  binStr = bin(num)
  if int(binStr[2]) == 1 and int(binStr[3:]) == 0 \
    and len(binStr[3:]) % 2 == 0:
      return True
return False

Solution 1 Alternate: String Slicing variation

This solution converts the string to a binary representation again, makes sure there’s only a single 1, then looks for the position of that 1. If its position is evenly divisible by 2, then it’s a power of 4.

def isPowerOfFour(self, num):
   if num <= 0:
     return False
   n = bin(num)[::-1]
   if n.count(‘1’) > 1:
     return False
   pos = n.index(‘1’)
   return pos % 2 == 0

Solution 2: Bitwise

For a detailed explanation of bitwise, I really like this article: https://www.hackerearth.com/practice/notes/bit-manipulation/

My intention here is to explain just enough so the code makes sense, once you understand a bit about bitwise (see how I did that?)

Solution 2 Variation One: Bitwise & between num & 0x55555555 == num

return num > 0 and num & (num-1) == 0 and 0x55555555 & num == num
NOTE: 
hex 0x55555555 = 
binary 0b1010101010101010101010101010101 =
int 1431655765 (which seems really random to me. LOL)

Bitwise Variation Two:

return num > 0 and num & (num-1) == 0 and 0xAAAAAAAA & num == 0
NOTE: 
hex 0xAAAAAAAA = 
0b10101010101010101010101010101010 = 
int 2863311530 (also seems random)

In the two variations, the first two parts of the statements are identical

Statement Parts 1 & 2:

The first part makes sure the number is above 0. Negative numbers are outside the scope of the challenge.

The second part tests if the number is a power of two. It does this by using a bitwise AND(&). If a number is a power of two, a bitwise & between the number & one less than the number, returns 0. Here’s an example of how it does this:

Example 1:
num = 64
num - 1 = 63
Rule for bitwise &: If both numbers in a column are 1, the comparison result is 1, otherwise, the comparison result is 0
Bitwise comparison column by column
00000000000000000000000001000000  # bin(64)
00000000000000000000000000111111  # bin(63)
----------------------------------
00000000000000000000000000000000 == 0 == True for num & num-1 == 0
Example 2:
num = 32 (a power of 2, but NOT a power of 4...power of four is after this)
num - 1 = 31
Rule for bitwise &: If both numbers in a column are 1, the comparison result is 1, otherwise, the comparison result is 0
Bitwise comparison column by column
00000000000000000000000000100000 # bin(32)
00000000000000000000000000011111 # bin(31)
----------------------------------
00000000000000000000000000000000 == 0 so num & num-1 is True
Example 3:
num = 14
num - 1 = 13
Bitwise comparison column by column
00000000000000000000000000001110 # bin(14)
00000000000000000000000000001101 # bin(13)
----------------------------------
00000000000000000000000000001100 == 12 so num & num-1 is False. Fourteen (14) isn't a power of 2

Statement Part 3: Two Variations on A Bitwise Theme

The third part has two variations, but they both do essentially the same thing; they determine whether the number (which has already been established as a power of 2 in the previous step) is ALSO a power of four.

Variation 1: hex 0xAAAAAAAA & num == num 
(hex 0xAAAAAAAA = binary 0b1010101010101010101010101010101)
or
Variation 2: hex 0x55555555 & num == 0 
(hex 0x55555555 = binary 0b10101010101010101010101010101010)

The first variation returns the original number if it’s a power of 4.
The second variation returns a 0 if it’s a power of 4.

VARIATION ONE EXAMPLES:
Example 1: Num = 64
Desired result: Bitwise & returns the original number
Rules for bitwise &:  If both numbers in a column are 1, the comparison result is 1, otherwise, the comparison result is 0
Bitwise comparison column by column
0b1010101010101010101010101010101
0b0000000000000000000000001000000
---------------------------------
0b0000000000000000000000001000000 == 64 (2 ^6)
Result: Bitwise & comparison between the above two - equals 64, so this part is True.  Because all three parts of the statement are true for 64, the whole statement returns True
#*************************************************************
Example 2: Num = 32 
Remember: All values except powers of 2 were eliminated in the 2nd part of the statement
Desired result: Bitwise & returns the original number
Rules for bitwise &:  If both numbers in a column are 1, the comparison result is 1, otherwise, the comparison result is 0
Bitwise comparison column by column
0b1010101010101010101010101010101
0b0000000000000000000000000100000
---------------------------------
0b0000000000000000000000000000000 == 0 Uh-oh, it's not 32
Result: 32 isn't a power of 4.  This part of the statement is False, so the whole shootin' match returns False

Variation Two Examples: The only difference between this one is that we WANT the result to be 0, NOT the original number, because what it’s being compared to is different by 1.

VARIATION TWO EXAMPLES:
Example 1: Num = 64
Desired result: Bitwise & returns the original number
Rules:  If both numbers in a column are 1, the comparison result is 1, otherwise, the comparison result is 0
Bitwise comparison column by column
0b10101010101010101010101010101010
0b00000000000000000000000001000000
---------------------------------
0b0000000000000000000000001000000 == 64 (2 ^6) is True
Result: Bitwise & comparison between the above two returns 64, so this part is True.  
Because all three parts of the statement are true for 64, the whole statement returns True
#*************************************************************
Example 2: Num = 32 
Remember: All values except powers of 2 were eliminated in the 2nd part of the statement
Desired result: Bitwise & returns the original number
Rules for bitwise &:  If both numbers in a column are 1, the comparison result is 1, otherwise, the comparison result is 0
Bitwise comparison column by column
0b1010101010101010101010101010101
0b0000000000000000000000000100000
---------------------------------
0b0000000000000000000000000000000 == 0 Uh-oh, False
Result: 32 isn't a power of 4.  
This part of the statement is False, so the whole shootin' match returns False

Maybe you didn’t need this much detail? It’s difficult to figure out where the line is between too much explaining: (“This is a computer, this is a mouse” ) and not enough: “Here’s a screwdriver and some parts. Lemme know when you’re done.”

If you had a different solution to this challenge, or have something to say about my solutions, please do share! And if you’re writing a blog here on Medium, let me know. I’d love to read what you’ve written, too.

P.S. Writing this blog took HOURS longer than solving the problem. That’s a good sign; it wasn’t always like that.