Power of Two

Easy
0/40
Average time to solve is 15m
profile
Contributed by
58 upvotes
Asked in companies
SamsungQualcommInfosys

Problem statement

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.


For example:
'N' = 4,
4 can be represented as 2^2. So, 4 is the power of two, and hence true is our answer.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
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.
Sample Input 1:
16
Sample Output 1:
true
Explanation of Sample Input 1:
16 can be represented as 2^4. So, 16 is the power of two, and hence true is our answer.
Sample Input 2:
10
Sample Output 2:
false
Constraints:
-2^31 <= 'N' <= 2^31 - 1

Time Limit: 1sec
Hint

Recursively, keep dividing the number by 2 till it reaches 1 or any odd number.

Approaches (3)
Recursive Approach

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.

Time Complexity

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)).

Space Complexity

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)).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Power of Two
Full screen
Console