Amazon Interview Solution: Power of 2

Given a positive integer N. The task is to check if N is a power of 2. That is N is 2^x for some x.
Input:
The first line contains T denoting the number of test cases. Each test case contains a single positive integer N.
Output:
Print "YES" if it is a power of 2 else "NO" (Without the double quotes).
Constraints:
1 <= T <= 100
0 <= N <= 10¹⁸
Example:
Input :
2
1
98
Output :
YES
NO
Explanation:
Testcase 1:  1 is equal to 2 raised to 0 (2⁰ == 1).

Solution : The best solution is a little bit tricky. But it is O(1) solution which is the best. if N is the number then if the & operation of N & N-1 is 0 then it will be power of 2 else it will not. Example: 8. Binary is 1000 and binary of 7 is 0111. 1000 & 0111 is 0000. So 8 (2^3) is power of 2.

Code

#include<iostream>
using namespace std;
int main()
 {
    //code
    long long int i,j,k,l,m,n,t;
    cin>>t;
    for(i=1;i<=t;i++)
    {
        cin>>n;
        if(n>0)
        {
            k=n & n-1;
            if(k==0)
            {
                cout<<"YES"<<endl;
            }
            else
            {
                cout<<"NO"<<endl;
            }
        }
        else
        {
            cout<<"NO"<<endl;
        }
       
    }
    return 0;
}

 

Download Coding Interview Book and Get More Tutorials for Coding and Interview Solution: Click Here

Download System Design Interview Book and Get More Tutorials and Interview Solution: Click Here

Do you need more Guidance or Help? Then Book 1:1 Quick Call with Me: Click Here

Share on Google Plus

About Ashadullah Shawon

I am Ashadullah Shawon. I am a Software Engineer. I studied Computer Science and Engineering (CSE) at RUET. I Like To Share Knowledge. Learn More: Click Here