Problem of the day
You have been given an integer 'N'.
Your task is to return true if it is a power of two. Otherwise, return false.
An integer 'N' is a power of two, if it can be expressed as 2 ^ 'K' where 'K' is an integer.
'N' = 4,
4 can be represented as 2^2. So, 4 is the power of two, and hence true is our answer.
The only line contains an integer 'N'.
Output Format:
The only line contains "true" if the integer 'N' is a power of 2 otherwise "false".
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
16
true
16 can be represented as 2^4. So, 16 is the power of two, and hence true is our answer.
10
false
-2^31 <= 'N' <= 2^31 - 1
Time Limit: 1sec
Recursively, keep dividing the number by 2 till it reaches 1 or any odd number.
Recursive approach is to keep dividing the number by two, i.e. do ‘N’ = ‘N’/2 recursively. In any case, if ‘N’%2 becomes non-zero and ‘N’ is not 1 then ‘N’ is not a power of 2. If ‘N' becomes 1 then it is a power of 2.
O(Log2(N)), where ‘N’ is the given number.
Since, we are doing a maximum of Log2(N) number of recursive calls to reach the base case, thus, the time complexity will be O(Log2(N)).
O(Log2(N)), where ‘N’ is the given number.
We are using O(H) extra space for the call stack where ‘H’ is the height of the recursion stack, and height of a recursion stack could be Log2(N) in the worst case. Thus, the final space complexity is O(Log2(N)).