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

[toc]

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 == 2^k.

Constraint: -2³¹ <= n <= 2³¹ - 1

Examples

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

Example 1:
Input: n = 1
Output: True
Explanation: 2⁰ = 1

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

Example 3:
Input: n = 3
Output: False

Example 4:
Input: n = 4
Output: True
Explanation: 2² = 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.

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.

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.