Power of Two

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.

Sample Input

4

Sample Output 

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).

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;
}

Output

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;
}

Output

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