Is A Power Of 2
Try First, Check Solution later1. You should first read the question and watch the question video.2. Think of a solution approach, then try and submit the question on editor tab.3. We strongly advise you to watch the solution video for prescribed approach.
1. You are given a number n.Input Format
2. You have to check whether it is a power of 2 or not.
A number nOutput Format
1 <= n <= 10^9Sample Input
In this problem, we have to determine whether a given integer input is a power of 2 or not.
For example, 1, 2, 4, 8, 16, 32 ... are numbers that are a power of 2.
We will implement a constant time solution with bit manipulation.
A common trait of any number which is a power of 2 is that it has only one set bit and the rest of all bits are unset and that set bit is the MSB bit.
We can approach the problem in multiple ways. One way is to count the number of set bits using Kerninghams algorithm. Another approach deals with taking an AND operation with (N - 1). This works as N should be of type 1 0 0 0 ... while (N - 1) will be of type 0 1 1 1 ... so their AND operation must be zero for the number to be a power of 2. Another approach can be to get the rightmost set bit mask of the number and as there is only one set bit for a power of 2 number so the value of the RSB mask must be equal to the number N for it to be a power of 2.
Time Complexity: O(1)
The time complexity for the function is constant.
Space Complexity: O(1)
The space complexity for the function is constant.
Asked in Companies