231. Power of Two - Explanation

Description

You are 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).

Example 1:

Input: n = 1

Output: true

Explanation: (2^0) is 1.

Example 2:

Input: n = 8

Output: true

Explanation: (2^3) is 8.

Example 3:

Input: n = 12

Output: false

Constraints:

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

We can generate all powers of two by starting from 1 and repeatedly multiplying by 2. If we reach exactly n, then n is a power of two. If we exceed n without matching it, then it's not.

Algorithm

If n is less than or equal to 0, return false.
Start with x = 1.
While x is less than n, multiply x by 2.
Return true if x equals n, false otherwise.

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

        x = 1
        while x < n:
            x *= 2
        return x == n

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

2. Recursion

Intuition

A number is a power of two if we can repeatedly divide it by 2 until we reach 1. If at any point the number is odd (and not 1), it cannot be a power of two.

This recursive approach reduces the problem by half at each step.

Algorithm

If n equals 1, return true (2^0 = 1).
If n is less than or equal to 0, or n is odd, return false.
Recursively check if n / 2 is a power of two.

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

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(\log n)$ for recursion stack.

3. Iteration

Intuition

The same logic as recursion, but implemented with a loop. We keep dividing by 2 (or right-shifting by 1) as long as the number is even. If we end up with 1, the original number was a power of two.

Algorithm

If n is less than or equal to 0, return false.
While n is even (divisible by 2), right-shift n by 1.
Return true if n equals 1, false otherwise.

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

        while n % 2 == 0:
            n >>= 1
        return n == 1

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

4. Bit Manipulation - I

Intuition

In two's complement representation, -n flips all bits of n and adds 1. For a power of two (which has exactly one set bit), n & (-n) isolates the lowest set bit. If n is a power of two, this equals n itself since there's only one bit set.

Algorithm

Check that n is positive.
Compute n & (-n) to isolate the lowest set bit.
Return true if this equals n, meaning n has exactly one set bit.

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

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

5. Bit Manipulation - II

Intuition

Powers of two in binary have exactly one bit set (1, 10, 100, 1000, ...). Subtracting 1 from such a number flips all bits from the rightmost set bit onward. For example, 8 (1000) minus 1 equals 7 (0111).

ANDing n with n - 1 clears the lowest set bit. If n is a power of two, this results in 0 since there was only one bit to clear.

Algorithm

Check that n is positive.
Compute n & (n - 1) to clear the lowest set bit.
Return true if the result is 0, meaning n had exactly one set bit.

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

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

6. Math

Intuition

The largest power of two that fits in a 32-bit signed integer is 2^30 (since 2^31 exceeds the positive range). Any smaller power of two must divide evenly into 2^30.

If n is a power of two, then 2^30 mod n equals 0. If n is not a power of two, the division will have a remainder.

Algorithm

Check that n is positive.
Compute (1 << 30) % n (i.e., 2^30 mod n).
Return true if the result is 0.

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

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

Common Pitfalls

Forgetting to Handle Non-Positive Numbers

A common mistake is forgetting that n must be strictly positive. Zero and negative numbers cannot be powers of two, but the bit manipulation tricks like n & (n - 1) == 0 will incorrectly return true for n = 0. Always check n > 0 before applying bit operations.

Integer Overflow in Iterative Approaches

When iteratively multiplying by 2 (e.g., x *= 2), the variable can overflow if using a 32-bit integer type. In languages like Java or C++, use a long or long long type for the accumulator to avoid wrapping around to negative values before reaching large inputs like 2^30.