Power of Two

Problem

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 == 2^x.

Examples

Example 1:

Input: n = 1
Output: true
Explanation: 20 = 1

Example 2:

Input: n = 16
Output: true
Explanation: 24 = 16

Solution

Method 1 - Simple Division and Modulo Operator - Iterative Approach

We divide a number (N) by 2 repeatedly. If it remains even and reaches 1, N is a power of 2. However, division by zero is undefined, so N cannot be a power of 2 if it's zero.

Code

Java

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

Complexity

• ⏰ Time complexity: O(log n)
• 🧺 Space complexity: O(1)

Method 2 - Simple Division and Modulo Operator - Recursive Approach

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

Complexity

• ⏰ Time complexity: O(log n)
• 🧺 Space complexity: O(1)

Method 3 - Count Bits with user-defined function

boolean isPowerOfTwo(int n) {
	int count = 0;
	while (n > 0) {
		if ((n & 1) == 1) {
			count++;
		}
		n = n >> 1;
	}
	return count == 1 ? true : false;
}

We can make it slightly faster:

boolean isPowerOfTwo(int n) {
	int count = 0;
	while (n > 0) {
		if ((n & 1) == 1) {
			count++;
			if (count > 1) {
				return false
			}
		}
		n = n >> 1;
	}
	return count == 1 ? true : false;
}

Method 4 - Count Bits with Standard Library

public boolean isPowerOfTwo(int n) {
	return n>0 && Integer.bitCount(n) == 1;
}

Method 5 - Using Bitwise and with N & (N-1)

boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n-1)) == 0;
}

Why N&(N-1) works? Read more here - [Explain (n & (n-1)) == 0](explain-n-n-1-0).

Method 6 - Using Logarithms

bool isPowerOfTwo(int n) {
    return floor(log2(n)) == ceil(log2(n)) && n!=0 ? true : false;
}

Above solution easily works in c++, for java:

public boolean isPowerOfTwo(int n) {
	if(n==0)
		return false;
    return (int)(Math.ceil(Math.log10(n)/Math.log10(2))) == (int)(Math.floor(Math.log10(n)/Math.log10(2)));
}

Note that above code works for Math.log10 but doesn't for Math.log.

Method 7 - Using Integer.Max_Value and Division

Because the range of an integer = -2147483648 (-2^31) ~ 2147483647 (2^31-1), the max possible power of two = 2^30 = 1073741824.

1. If n is the power of two, let n = 2^k, where k is an integer. We have 2^30 = (2^k) * 2^(30-k), which means (2^30 % 2^k) == 0.
2. If n is not the power of two, let n = j*(2^k), where k is an integer and j is an odd number.

We have (2^30 % j*(2^k)) == (2^(30-k) % j) != 0.

return n > 0 && (1073741824 % n == 0);

Complexity

• ⏰ Time complexity: O(1)
• 🧺 Space complexity: O(1)