# Leetcode: Power of Two Python Solution

# 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 - 00012 - 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!