Power of 2 - InterviewBit Solution

Problem: Power of 2

Problem Description:

Find if the given number is a power of 2 or not. More specifically, find if the given number can be expressed as 2^k where k >= 1.

Input:

number length can be more than 64, which mean number can be greater than 2 ^ 64 (out of long long range) 

Output:

return 1 if the number is a power of 2 else return 0  

Example:

Input : 128 
Output : 1

Solution Approach:

Method 1: (Will not work for very large numbers)

You can count the number of bits as if the number is a power of two which means it contains only a single set bit in its binary representation. To find if a number has only one set bit or not, we have a number of ways. First, keep dividing it by 2 until the number becomes 0, and if the number is not divisible by 2 only once, then it is a power of 2. For this time complexity would be O(logN), because each time we are reducing it by 2.

Another interesting way to find is using bit operations. You will notice that, in a binary representation, if a number is just smaller than a power of 2, then it would have all the bits asset.

For example:

0 - (0)
1 - (1) 

1 - (01)
2 - (11)

7 - (0111)
8 - (1000)

15 - (01111)
16 - (10000)

When you take the bitwise "&" of these pairs, you will find that all of them would return 0. So you just have to check if N & (N-1) is 0 then it is a power of 2, otherwise not.

Time Complexity: O(1)

Space Complexity: O(1)

Solution:

Code in C++:

Method - 2 :

( It is simple and Brute force but will work for numbers larger than 2^64)

Time Complexity: O(N*Log(a))

Space Complexity: O(N),

where N is the length of String and "a" is the number itself.

If you have any questions or queries, feel free to drop a comment in the comments section below.

Note: Help us improve this blog

If you have a better solution, and you think you can help your peers to understand this problem better, then please drop your solution and approach in the comments section below.

We will upload your approach and solution here by giving you the proper credit so that you can showcase it among your peers.