Power of Two Leetcode Solution

We are given an integer and the goal is to check whether the integer is a power of two, that is, it can be represented as some whole power of '2'.

 

Example

16

Yes

13

No

Approach

A trivial solution can be: Check if all prime factors of the integer are all '2'. The time complexity of this method would be O(log2N). In order to do it in an optimal way, we can take help of Bit manipulations.

 

"Any number which is a power of two can only have a single bit set in binary representation"

 

How can it be checked that there is only a single bit set in the binary form?

 

Consider any number, x.

 

Now, if x is some power of two, then (x - 1) will turn off all the right bits to the set bit(set them as '0') and the set bit would be unset.

 

x = 8, x - 1 = 7

 

So, using BITWISE-AND of x and (x - 1), we can say if a number is some power of two, then, x & (x - 1) = 0

Algorithm(Trivial)

 

- Keep dividing the number by '2' until it is not divisible by '2' anymore.

- If the number is equal to '1':

 

- The integer is a power of two

 

- Else

 

- The integer is not a power of two

 

Algorithm(Bit-Manipulation)

 

- Check if x & (x - 1) is equal to zero

 

- If yes, the number is a power of 2

- The integer is not a power of 2, otherwise

 

Implementation

C++ Program of Power of Two Leetcode Solution

Naive Method

#includ

 

www.tutorialcup.com/leetcode-solutions/power-of-two-leetc...

Done