Home » Technical Interview Questions » Array Interview Questions » Power of Two

Power of Two


Reading Time - 2 mins

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.
READ  Count pairs from two sorted arrays whose sum is equal to a given value x

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

Power of Two

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

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions