Leetcode: Power of Two Python Solution

Celine Surai

Dec 24, 2020·2 min read

The Question

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 x such that n == 2x.

We are given a couple of examples to demonstrate how the output should look like:

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

This is a leetcode easy question, hence it is expected that you should easily find an optimal solution for this problem. We are going to look at two different approaches for this problem.

Approach 1

A number that is a power two has a modulus zero when divided by 2. Hence we can use this fact to check whether numbers are powers of two. The time complexity using this method will be 0(log n) and a space complexity of 0(n)

Here is the solution in code:

We can make our solution more optimal by making the space complexity 0(1)

Approach 2.

When we write numbers in their binary form, you realize that all numbers that are a power of two have only one ( digit that is 1). For instance look at the table below of numbers in their binary form:

1 - 0001 2 - 00103 - 00114 - 01005 - 0101 8 - 100016 - 10000

How to solve the question: We will go ahead and calculate n & (n-1).
The above expression equals n with its rightmost set bit cleared. That means the rightmost 1 in the binary representation of n is made 0.

If n is a power of two n & (n-1) will equals to zero. Hence using this notion we can check whether a number is a power of two.

Here is the solution in code:

The time and space complexity here is 0(1) which makes it more optimal than the previous solution.

And that is how to approach this problem in an interview setting! Feel free to have a look at this video tutorial for a more descriptive solution.

Happy Coding!