Power Of Two Editorial

Practice Problem Link: Power Of Two

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a number n, check whether it is a power of two or not. An integer n is a power of two, if there exists an integer x such that n = 2x.

Naive Approach

The naive approach is to keep dividing the number by 2 and counting the number of set bits in the number, till the number is reduced to zero. If the number of set bits is equal to 1, then return true, else false.

Analysis

• Time Complexity: O(log n)
• Space Complexity: O(1)

Implementation

C++

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

Java

class Solution {
    boolean isPowerOfTwo(int n) {
        int count = 0;
		while(n != 0) {
			if(n % 2 == 1) {
				count++;
			}
			n /= 2;
		}
		return count == 1;
    }
}

Optimal Approach

The optimal is to observe that if a number n is a power of 2, then its bitwise & with n - 1 will be 0. Using this fact we can check if a number is the power of 2. The special case to check is if n = 0 separately.

Analysis

• Time Complexity: O(1)
• Space Complexity: O(1)

Implementation

C++

bool isPowerOfTwo(int n) {
    if(n == 0) {
		return false;
	}
	return !(n & (n - 1));
}

Java

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