Welcome back, dear reader. So, how is it going? So, today we will discuss a very simple problem called POWER OF TWO. So, what does this problem say? We are given a number n. We have to tell whether the number n is an absolute power of two or not. For instance, if we get the input as 16, we will print true as 16 is an absolute power of 2 whereas if we get the input as 17, we will print false as it is not an absolute power of 2.
- Take the input number from the user and subtract 1 from it.
- Take the logical AND of n and n-1.
- If the logical AND of n and n-1 is 0, the number n is an absolute power of two else it is not.
Let us see some absolute powers of 2 and learn some facts about them. Have a look at the image shown below:
Do you notice anything in these powers of 2? IIf you have a look at them carefully, 2 0 has zero 0's and 2 1 has one 0. Similarly, 2 2 has 2 0's after a one and so on. So, 2 x is of form 100......0 where there are x 0's present after 1.
Now think of some bitwise operation that we have already studied and try to relate it to this table above.
Have a look at the image shown below:
So, 1<<0 is 2 0 and 1<<1 is 2 1 and 1<<2 is 2 2, and so on. So, 1<<x=2 x . Ok!!
So, we got this much, but how is it useful to us? Well, this is all just for the sake of your knowledge so that you can use these concepts in bigger problems that we will solve ahead of this problem. We have some more interesting concepts for you regarding this. Let us discuss those quickly and then we will discuss the solution to this problem (which is quite simple).
Some more Facts for You
As we have already discussed above, 1<<x=2 x . But, this is only about 1<<x. What do we mean by a<<b? Can you think about it? Let us see this with the help of an example shown below:
As you can see above when we left shift 'a' by 1, it gets multiplied by 2. If we perform a<<2, it will get multiplied by 4.
So, in a nutshell, we can say that if we do a<<b, we are doing a x 2 b . Similarly, we want you to try this on the right shift operator as well. As in the above case, we saw that 1<<x gives us 2 x similarly try to find out the value of 1>>x yourself using the same logic as we have used in the diagrams above.
You will find out that 1>>x means 2 -x and a>>b means a x 2 -b . So, doing the left shift by 1 once means multiplying a number by two, and doing the right shift by 1 means that we are dividing the number by two.
Now we have gained enough knowledge for the further questions to be solved and learned a lot of facts about the absolute powers of 2, let us now learn how to solve this question.
So, we know that the numbers that are absolute powers of 2 have 1 at the MSB and have x zeroes where x is the power of 2. Let us take the example of 2 7 .
So, we can see that the value of n AND n-1 is 0. This is a property for all the absolute powers of 2. So, if a number is an absolute power of 2 then n AND n-1 will be 0.
We recommend you watch the solution videoto understand the concepts that we have discussed till here completely.
The above code is very simple and it is completely based on the facts that we have studied above. Still, if you have any doubts regarding it, refer to the solution video below to clear them. Now that we have discussed the code and the procedure, let us discuss the time and space complexity.
Time and Space Complexity Analysis
Time Complexity:The time complexity of the above solution is O(1) as we have just used some bitwise operators which work in constant time.
Space Complexity:The space complexity is also O(1) as we have not used any extra space.
So, dear reader, we hope that you have understood the above procedure completely. If you still have any doubts related to it, refer to the complete solution video complete solution video to clear all your doubts. With this, we have completed this problem.
Here are some suggestions from our side that you do not want to miss:
- We suggest that you should watch the complete solution video once so that you do not miss out on any little concept that has been explained in it.
- We also suggest that you try to analyze the right shift operator yourself in the same way as we have analyzed the left shift operator. This will give you more insight into the concepts. Till then, Happy Coding!!!!