[toc]

**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`

^{31} <= n <= 2^{31} - 1

**Examples**

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

Example 1:Input: n = 1 Output: True Explanation: 2 ^{0} = 1Example 2:Input: n = 16 Output: True Explanation: 2 ^{4} = 16Example 3:Input: n = 3 Output: False Example 4:Input: n = 4 Output: True Explanation: 2 ^{2} = 4Example 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 1n = 1 print(power_of_two(n)) # True# Example 2n = 16 print(power_of_two(n)) # True# Example 3n = 3 print(power_of_two(n)) # False# Example 4n = 4 print(power_of_two(n)) # True# Example 5n = 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 1n = 1 print(power_of_two(n)) # True# Example 2n = 16 print(power_of_two(n)) # True# Example 3n = 3 print(power_of_two(n)) # False# Example 4n = 4 print(power_of_two(n)) # True# Example 5n = 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 1n = 1 print(power_of_two(n)) # True# Example 2n = 16 print(power_of_two(n)) # True# Example 3n = 3 print(power_of_two(n)) # False# Example 4n = 4 print(power_of_two(n)) # True# Example 5n = 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

function takes one integer argument and returns a binary string with prefix **bin(integer)**`"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:is a critical life skill in today’s world that’s shaped by the web and remote work.**extracting data programmatically from websites** - 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.