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

Rate this post

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 