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

Rate this post

[toc]

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: `-231 <= n <= 231 - 1`

## Examples

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

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.

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.

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-LinerUsingBit 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