# Power of Two Leetcode Solution  Difficulty Level Easy
algorithms Bit Manipulation Bits coding Interview interviewprep LeetCode LeetCodeSolutions Math

We are given an integer and the goal is to check whether the integer is a power of two, that is, it can be represented as some whole power of ‘2‘. `16`
`Yes`
`13`
`No`

## Approach  A trivial solution can be: Check if all prime factors of the integer are all ‘2‘. The time complexity of this method would be O(log2N). In order to do it in an optimal way, we can take help of Bit manipulations.

“Any number which is a power of two can only have a single bit set in binary representation”

How can it be checked that there is only a single bit set in the binary form?

Consider any number, x.

Now, if x is some power of two, then (x – 1) will turn off all the right bits to the set bit(set them as ‘0’) and the set bit would be unset.

x = 8, x – 1 = 7

So, using BITWISE-AND of x and (x – 1), we can say if a number is some power of two, then, x & (x – 1) = 0

## Algorithm(Trivial)  1. Keep dividing the number by ‘2’ until it is not divisible by ‘2’ anymore.
2. If the number is equal to ‘1’:
• The integer is a power of two
3. Else
• The integer is not a power of two
Sliding Window Technique

## Algorithm(Bit-Manipulation)  1. Check if x & (x – 1) is equal to zero
• If yes, the number is a power of 2
• The integer is not a power of 2, otherwise

## Implementation  ### C++ Program of Power of Two Leetcode Solution

#### Naive Method

```#include <bits/stdc++.h>
using namespace std;

bool powerOfTwo(int n)
{
while(n % 2 == 0)
n /= 2;
return (n == 1);
}

int main()
{
int n = 16;
if(powerOfTwo(n))
cout << "Yes" << '\n';
else
cout << "No" << '\n';

return 0;
}
```

#### Optimal Method

```#include <bits/stdc++.h>
using namespace std;

bool powerOfTwo(int n)
{
//16 = 
//15 = 
//16 & 15 = 0
return (n & (n - 1)) == 0;
}

int main()
{
int n = 16;
if(powerOfTwo(n))
cout << "Yes" << '\n';
else
cout << "No" << '\n';

return 0;
}
```
`Yes`

### Java Program of Power of Two Leetcode Solution

#### Naive Method

```class power_of_two
{
public static boolean powerOfTwo(int n)
{
while(n % 2 == 0)
n /= 2;
return (n == 1);
}

public static void main(String args[])
{
int n = 16;
if(powerOfTwo(n))
System.out.println("Yes");
else
System.out.println("No");
}
}
```

#### Optimal Method

```class power_of_two
{
public static boolean powerOfTwo(int n)
{
return (n & (n - 1)) == 0;
}

public static void main(String args[])
{
int n = 16;
if(powerOfTwo(n))
System.out.println("Yes");
else
System.out.println("No");
}
}
```
`Yes`

## Complexity Analysis  ### Time Complexity of Power of Two Leetcode Solution

The time complexity of Naive Approach is O(log2N), where N = given integer. However, the optimal approach is faster, as Bitwise-And is faster and therefore has a time complexity of O(1).

### Space Complexity of Power of Two Leetcode Solution

Only space used in the program is the function signature. Therefore, constant space is used – O(1).