Leetcode Question 231. Power of Two [ Intuition, Approach, Solution, Complexities ]

Description :- Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that n == 2x.

Example 1:

Input: n = 1
Output: true
Explanation: 20 = 1

Example 2:

Input: n = 16
Output: true
Explanation: 24 = 16

Example 3:

Input: n = 3
Output: false

Constraints:

-231 <= n <= 231 - 1

Intuition :-

This Leetcode question simply says, we need to find out whether the given number is Power of Two or not and can we solve this question without any loop. Also it indicates that numbers must be greater than 0 otherwise its return true instead of false.

Approach :- for a simple Brute-force approach, we can simply go through a for loop and some do some operations inside it to check if the number is most probably equal to the given number and some basic maths calculations.

Code here :-

bool isPowerOfTwo(int n) {
int num = 1;
for(int i=0;i<n;i++){
if(num == n){
return true;
}
num = num*2;
}
return false;
}

Although this code will give error while submitting due to overflow of signed integer value of num = num*2, However it’ll also give us O(log n) Time complexity and O(1) space complexity.

Now if we come to the straight forward most optimal approach, we can calculate/solve the same using bit manipulation or in other words some says “Bit Masking”

Now the same code becomes of a one liner only

bool isPowerOfTwo(int n) {
return (n & (n-1)) == 0 ? true : false;
}

but this code surely give us error while submitting as its not following the <= 0 values, so the formatted and correct code for this issues is

bool isPowerOfTwo(int n)
{
return (n >0 and (n & (n-1))) == 0 ? true : false;
}

So, this code generally don’t use any space as above and the time complexity is also reduces from O(log n) to O(1).

Verdict :- Cheers! We solved the PowerOfTwo.