Question

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

Solution

Approach 1

In this solution, first we will check if the number is divisible by 2 (even number). If it is divisible by 2, we will keep on dividing the number by two, and get the quotient, i.e., do n = n/2 iteratively. In any iteration, if n%2 becomes odd and is not equal to 1, then n is not a power of 2. If n becomes 1 then it is a power of 2.

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n<0 or n==0:
            return False
        i = n

        if(i>0):
            while(i%2)==0:
                i = i/2
            if i== 1:
                return True
            else:
                return False

Time Complexity: O(logn)

Auxiliary Space: O(1)

Approach 2

To check if a given number is a power of 2, we will use bit manipulation technique. If the & operation between the given number n and given number minus one  n-1 gives us 0, it is a power of 2. If it is not 0,then it is not a power of two.

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n == 0:
            return False
        ans = n & (n-1)
        if ans == 0:
            return True
        else:
            return False

Time Complexity: O(1)

Auxiliary Space: O(1)