[Google Interview] How To Solve The Power of Two Problem In Python

Power of Two [Google Interview]

Company Tags: Google, Amazon, Apple

As reported by various programmers, this is one of the interview questions that have occurred in interviews quite a lot. Will you be able to solve it optimally if asked in your interview?

Problem Formulation

You are given an integer n; return true if it is a power of two. Otherwise, return false.

  • An integer n is a power of two if there exists an integer k such that n == 2k.

Constraint: -231 <= n <= 231 - 1

Examples

Let us look at some examples to improve our understanding of the problem.

Example 1:
Input: n = 1
Output: True
Explanation: 20 = 1

Example 2:
Input: n = 16
Output: True
Explanation: 24 = 16

Example 3:
Input: n = 3
Output: False

Example 4:
Input: n = 4
Output: True
Explanation: 22 = 4

Example 5:
Input: n = 5
Output: False

Now that you have a clear understanding of the problem, let’s dive into the methods to solve it.

Brute Force Method: Iterative Approach

Approach: In this approach, you have to keep performing an integer division, i.e., n // 2 as long as n mod 2 is 0. Keep repeating this until n%2 yields 0. Finally, if the value represented by n is 1, it means that the given value of n is indeed a power of two. Hence, return True. Otherwise, return False.

The following illustration will help you to understand the approach better:

 

Solution:

def power_of_two(n):
    if n <= 0:
        return False
        
    while n % 2 == 0:
        n = n // 2
    
    if n == 1:
        return True
    else:	
        return False

Test Case Analysis: Let’s run this code on our examples.

# Example 1
n = 1
print(power_of_two(n))
# True

# Example 2
n = 16
print(power_of_two(n))
# True

# Example 3
n = 3
print(power_of_two(n))
# False

# Example 4
n = 4
print(power_of_two(n))
# True

# Example 5
n = 5
print(power_of_two(n))
# False

Hurrah! It passed all the test cases.

Complexity Analysis: Since you have to keep dividing the given integer by 2, the time complexity of this algorithm is O(log n).

Discussion: This in itself is an effective complexity. However, is there a way to produce a more efficient algorithm? Let’s find out in the next algorithm.

Optimal Solution: Bitwise AND &

Approach: The idea of this approach is to use the binary form of the given integer (decimal number). Then use the AND operator on the following numbers:- n and (n-1). If the output of ( n & (n-1) ) == 0 then the number is a power of two.

The trick that comes into play here is that each number n that is a power of 2 has a number that is one less, i.e., n-1 that has ones on the position n has zeroes. And a bitwise and of 0 and 1 is always 0. In all other cases, this computation will yield a number other than zero.

Examples:

Recap: Python’s bitwise AND operator x & y performs logical AND on each bit position on the binary representations of integers x and y. Thus, each output bit is 1 if both input bits at the same position are 1; otherwise, it’s 0. For example, the integer expression 4 & 3 is translated to binaries 0100 & 0011 which results in 0000 because all four input bit positions are different.
⦿Recommended Article: Python Bitwise AND Operator &

Solution:

def power_of_two(n):
    if n == 0:
        return False
        
    return (n - 1) & n == 0

Test Case Analysis: Let’s run this code on our examples.

# Example 1
n = 1
print(power_of_two(n))
# True

# Example 2
n = 16
print(power_of_two(n))
# True

# Example 3
n = 3
print(power_of_two(n))
# False

# Example 4
n = 4
print(power_of_two(n))
# True

# Example 5
n = 5
print(power_of_two(n))
# False

Eureka! It passed all the test cases.

Complexity Analysis: The time complexity of this method would be O(log n) because you keep dividing the number by 2 in every iteration.

Alternate Approach: One-Liner Using Bit Count

Approach: Another workaround to solve our problem optimally is to work upon the binary representation of the given integer and count the number of 1’s in it. If the number is a power of two, then it must contain only one “1” followed by 0’s.

For example:

Numbers that are the power of two:

  • The binary representation of 16 is 10000
  • The binary representation of 8 is 1000
  • The binary representation of 4 is 100

Numbers that are not the power of two:

  • The binary representation of 5 is 101
  • The binary representation of 3 is 011

Solution:

def power_of_two(n):
    return n > 0 and bin(n).count( '1' ) == 1

Test Case Analysis: Let’s run this code on our examples.

# Example 1
n = 1
print(power_of_two(n))
# True

# Example 2
n = 16
print(power_of_two(n))
# True

# Example 3
n = 3
print(power_of_two(n))
# False

# Example 4
n = 4
print(power_of_two(n))
# True

# Example 5
n = 5
print(power_of_two(n))
# False

Explanation: Here, n>0 ensures that the number is greater than 0 while bin(n).count( ‘1’) helps you to find the number of 1’s in the binary representation of the given integer.

Complexity Analysis: We solved the problem without the usage of any loop. The time complexity to use the count method is O(1). The and operation also has a time complexity of O(1). Hence the overall time complexity of this approach is also O(1).

Recap: Python’s built-in bin(integer) function takes one integer argument and returns a binary string with prefix "0b". If you call bin(x) on a non-integer x, it must define the __index__() method that returns an integer associated to x. Otherwise, it’ll throw a TypeError: object cannot be interpreted as an integer.

⦿Recommended Tutorial:
Python Bitwise Operators [Full Guide + Videos]
Python bin() Function

Conclusion

I hope you enjoyed this coding interview question. Please stay tuned and subscribe for more interesting coding problems.

 Post Credits: Shubham Sayon and Rashi Agarwal


Recommended: Finxter Computer Science Academy

  • One of the most sought-after skills on Fiverr and Upwork is web scraping. Make no mistake: extracting data programmatically from websites is a critical life skill in today’s world that’s shaped by the web and remote work.
  • So, do you want to master the art of web scraping using Python’s BeautifulSoup?
  • If the answer is yes – this course will take you from beginner to expert in Web Scraping.