[LeetCode] 231. Power of Two

Problem : https://leetcode.com/problems/power-of-two/

Iteration solution:

Time complexity = O ( Log N )

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        while n > 1:
            if n % 2 != 0:
                return False

            # n = n // 2
            n = n >> 1
           
        return n == 1

Recursion solution:

Time complexity = O ( Log N )

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 0:
            return False
        
        if n == 1:
            return True
        
        return n % 2 == 0 and self.isPowerOfTwo(n >> 1)

Bit manipulate solution:

Time complexity = O ( 1 )

 
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:   
        
        count = 0
        while n > 0 and count <= 1:
            count += n & 1
            n >>= 1
        
        return count == 1

Number may have only one bit equals to 1 if it is power of 2.

With that observation in mind, we have the one liner solution:

n & (n-1) can trim the first '1' bit from right.

n & (n-1) == 0 means number n only as one '1' bit.

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:    
        return n > 0 and (n - 1) & n == 0

n & (-n) can extract the firt '1' bit from right.

n & (-n) == n also means number n only as one '1' bit.

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and n & (-n) == n

Edited on 05/03/2021. Add the one liner solution.

Edited on 11/07/2021. Add the second one liner solution base on bit manipulation.