Solution For Power Of Two

Problem statement: Given an integer n, determine if it is a power of two.

Solution:

Approach #1 Brute Force

One simple way to find out whether a number n is a power of 2 is to keep dividing it by two as long as the result is an integer so that 2^n / 2^n-1 = 2^1 = 2.

If the result is 1, then n is a power of 2, otherwise not.

Algorithm:

1. If n == 0, return False.
2. While n % 2 == 0, divide n by 2.
3. If n == 1, return True, otherwise return False.

Time Complexity: O(log n)

Approach #2 Bitwise-AND

Another way to solve this problem is to use the bitwise-AND operator.

If n is a power of 2, it means that n is of the form 2^k, where k is a non-negative integer. In binary form, such a number has only one bit set to 1. For example,

2^3 = 8 (00001000 in binary)
2^5 = 32 (00100000 in binary)

Taking the bitwise-AND of n and n-1 removes the last set bit of n. If n is a power of 2, the result will be 0.

Algorithm:

1. If n == 0, return False.
2. Return n & (n-1) == 0.

Time Complexity: O(1)

Code (Python) – Approach #1 Brute Force

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

Code (Python) – Approach #2 Bitwise-AND

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

Code (Java) – Approach #2 Bitwise-AND

class Solution {
public boolean isPowerOfTwo(int n) {
return n != 0 && (n & (n-1)) == 0;
}
}

Note: The bitwise-AND operator & has lower precedence than !=, so the brackets are necessary.

Step by Step Implementation For Power Of Two

class Solution {
    
    // function to check if given number is power of two
    public boolean isPowerOfTwo(int n) {
        
        // if number is 0, it is not a power of two
        if(n == 0) {
            return false;
        }
        
        // loop until n becomes 1
        while(n != 1) {
            
            // if n is not divisible by 2, it is not a power of two
            if(n % 2 != 0) {
                return false;
            }
            
            // divide n by 2
            n = n / 2;
        }
        
        // if n becomes 1, it is a power of two
        return true;
    }
}

def isPowerOfTwo(n): 
  
    if (n == 0): 
        return False
    while (n != 1): 
            if (n % 2 != 0): 
                return False
            n = n // 2
              
    return True

var isPowerOfTwo = function(n) {
    
    // if n is less than or equal to 0, it is not a power of two
    if (n <= 0) {
        return false;
    }
    
    // if n is a power of two, then it's binary representation will only have one '1' bit
    // we can use the built-in function to count the number of '1' bits in a number
    return n.toString(2).split('0').length === 1;
};

bool isPowerOfTwo(int n) 
{ 
    if (n == 0) 
        return false; 
    while (n != 1) 
    { 
        if (n%2 != 0) 
            return false; 
        n = n/2; 
    } 
    return true; 
}

using System; 
  
class GFG { 
      
// Function to check whether  
// x is power of 2 
static bool isPowerOfTwo(int x) 
{ 
    // Condition to check 
    // if x is power of 2 
    if (x == 0) 
        return false; 
          
    return (x & (x - 1)) == 0; 
} 
  
// Driver Code 
public static void Main() 
{ 
    int n = 32; 
      
    if(isPowerOfTwo(n)) 
        Console.Write("Yes"); 
    else
        Console.Write("No"); 
} 
}