# Power of Two  Difficulty Level Easy
Bit Bit Manipulation Bits Math

In Power of Two problem we have given an integer, check if it is the power of 2 or not. A number in the power of two if it has only one set bit in the binary representation. Let’s see one example of a number that contains only one set bit. If our input is 16 then we can represent it in binary format like 10000. Here we see that only one bit is 1 which means the number represents in the power of 2. Now see one example in which a set bit is more than 1. If our input is 13 then we represent it in binary format like 1101. Here we see there are 3 set bits. So we can’t represent it in the form of 2^y where y is an integer greater than 0.

## Input Format  First-line containing an integer value N.

## Output Format  Print “true” if we represent it in a given format else print “false”.

## Constraints  • 1<=N<=10^18.

4

true

### Explanation

We know that already the binary representation of 4 is 100 which means only one set bit here. So we represent it in form 2^y(2^2).

Two Sum Leetcode Solution

## Iterative approach  • Negative numbers and zero can never be in form 2^y where y is an integer.
• check if n can be divided by 2. If yes, divide n by 2 and check it repeatedly.
• if at last n is reduced to 1 then n is a power of 2 else it is not the form 2^y where y is an integer.

## Implementation  ### C++ Program for Power of Two

```#include <bits/stdc++.h>
using namespace std;
bool isPowerOfTwo(int n) {
if (n <= 0) return false;
while (n%2 == 0) n/=2;
return n == 1;
}
int main()
{
int n=4;
int ans=isPowerOfTwo(n);
if(ans)
cout<<"true"<<endl;
else
cout<<"false"<<endl;
return 0;
}```

`true`

### Java Program for Power of Two

```public boolean isPowerOfTwo(int n) {
if (n <= 0) return false;
while (n%2 == 0) n/=2;
return n == 1;
}```

### Time complexity

O(log n) because at each step we are dividing the number by 2.

## Bit operation approach  • Negative numbers and zero can never be a power of 2.
•  If a number is power of 2 then ( n & (n-1) )==0 ## Implementation  ### C++ Program for Power of Two

```#include <bits/stdc++.h>
using namespace std;
bool isPowerOfTwo(int n) {
return (n > 0 && (n & (n-1)) == 0);
}
int main()
{
int n=4;
int ans=isPowerOfTwo(n);
if(ans)
cout<<"true"<<endl;
else
cout<<"false"<<endl;
return 0;
}```

`true`

### Java Program for Power of Two

``` public boolean isPowerOfTwo(int n) {
return (n>0&&(n & (n-1))==0);
}```

### Time Complexity

O(1) because using only single AND we can find whether the number satisfies the condition or not.

References