LeetCode 231 - Power of Two

The problem asks us to determine whether a given integer n is a power of two. A number is considered a power of two if it can be written in the form: where x is a non-negative integer.

leetcodeeasymathbit-manipulationrecursion

LeetCode Problem 231

Difficulty: 🟢 Easy
Topics: Math, Bit Manipulation, Recursion

Solution

Problem Understanding

The problem asks us to determine whether a given integer n is a power of two.

A number is considered a power of two if it can be written in the form:

$$n = 2^x$$

where x is a non-negative integer.

Some examples of powers of two are:

  • 1 = 2^0
  • 2 = 2^1
  • 4 = 2^2
  • 8 = 2^3
  • 16 = 2^4

The input is a single integer n, and the expected output is a boolean value:

  • Return true if n is a power of two
  • Return false otherwise

The constraints specify:

$$-2^{31} \le n \le 2^{31} - 1$$

This means the input can be negative, zero, or positive. Negative numbers can never be powers of two because powers of two are always positive. Zero is also not a power of two.

The problem includes a follow-up asking whether we can solve it without loops or recursion. This hint strongly suggests that there is a mathematical or bit manipulation property we should exploit instead of repeatedly dividing by two.

Several edge cases are important:

  • n = 0, which should return false
  • Negative numbers such as -8
  • n = 1, because 1 = 2^0
  • Numbers close to integer limits
  • Odd numbers greater than 1, which cannot be powers of two

A naive implementation can easily fail if it does not correctly handle non-positive values before applying bit operations.

Approaches

Brute Force Approach

The most straightforward approach is to repeatedly divide the number by 2.

The idea is simple:

  • If n is divisible by 2, divide it by 2

  • Continue until:

  • the number becomes 1, meaning it is a power of two

  • or the number is no longer divisible by 2, meaning it is not

For example, with n = 16:

  • 16 -> 8 -> 4 -> 2 -> 1

Since we eventually reach 1, the number is a power of two.

For n = 12:

  • 12 -> 6 -> 3

Now 3 is not divisible by 2, so the answer is false.

This approach works correctly because every power of two can be repeatedly halved until only 1 remains.

Although this method is already efficient enough for the given constraints, it still uses a loop. The follow-up encourages us to look for a more elegant constant-time solution.

Optimal Bit Manipulation Approach

The key observation comes from binary representation.

A power of two has exactly one bit set to 1.

Examples:

Decimal Binary
1 0001
2 0010
4 0100
8 1000

Now consider what happens when we subtract 1:

n Binary of n n - 1 Binary of n - 1
1 0001 0 0000
2 0010 1 0001
4 0100 3 0011
8 1000 7 0111

Notice an important property:

  • n has exactly one 1 bit
  • n - 1 turns that bit into 0 and changes all lower bits into 1

Therefore:

$$n & (n - 1) = 0$$

for every positive power of two.

For example:

8      = 1000
7      = 0111
----------------
8 & 7  = 0000

This gives us a very compact and efficient solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(log n) O(1) Repeatedly divides by 2
Optimal O(1) O(1) Uses bit manipulation property

Algorithm Walkthrough

Optimal Bit Manipulation Algorithm

  1. First, check whether n is less than or equal to 0.

Powers of two are always positive integers. If n <= 0, immediately return false. 2. Compute n & (n - 1).

This operation removes the lowest set bit from n. 3. If the result equals 0, return true.

A power of two contains exactly one set bit, so removing that bit leaves all bits as 0. 4. Otherwise, return false.

Numbers with multiple set bits will still have at least one remaining set bit after the operation.

Why it works

The correctness relies on a binary representation invariant.

A positive power of two always contains exactly one set bit. Subtracting 1 flips that set bit to 0 and converts all lower bits into 1. Performing a bitwise AND between these two numbers removes every set bit and produces 0.

Non-powers of two contain more than one set bit, so after the AND operation, at least one bit remains set, producing a nonzero result.

Python Solution

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

        return (n & (n - 1)) == 0

The implementation begins by handling invalid inputs. Since powers of two must be positive, any value less than or equal to zero immediately returns False.

The core logic is the expression:

(n & (n - 1)) == 0

This uses the binary property of powers of two. For a valid power of two, the operation clears the only set bit and produces zero.

The implementation is concise because the bit manipulation property completely captures the mathematical definition we need.

Go Solution

func isPowerOfTwo(n int) bool {
    if n <= 0 {
        return false
    }

    return (n & (n - 1)) == 0
}

The Go implementation is almost identical to the Python version because both languages support bitwise operators directly on integers.

One important detail is the explicit positivity check before the bit operation. Negative integers use two's complement representation, and applying the bit trick directly without validation could produce incorrect results.

Go integers are fixed-width machine integers, but the problem constraints comfortably fit within standard integer sizes.

Worked Examples

Example 1

Input:

n = 1

Binary representation:

1 = 0001

Compute:

Step Value
n 0001
n - 1 0000
n & (n - 1) 0000

Since the result is 0, return true.

Example 2

Input:

n = 16

Binary representation:

16 = 10000

Compute:

Step Value
n 10000
n - 1 01111
n & (n - 1) 00000

Since the result is 0, return true.

Example 3

Input:

n = 3

Binary representation:

3 = 0011

Compute:

Step Value
n 0011
n - 1 0010
n & (n - 1) 0010

The result is not 0, so return false.

Complexity Analysis

Measure Complexity Explanation
Time O(1) Uses a constant number of operations
Space O(1) No extra memory proportional to input size

The algorithm performs only a few arithmetic and bitwise operations regardless of the input value. No loops, recursion, or additional data structures are used, so both time and space complexity remain constant.

Test Cases

solution = Solution()

assert solution.isPowerOfTwo(1) == True       # smallest power of two
assert solution.isPowerOfTwo(2) == True       # simple positive case
assert solution.isPowerOfTwo(4) == True       # another power of two
assert solution.isPowerOfTwo(16) == True      # larger power of two
assert solution.isPowerOfTwo(1024) == True    # large power of two

assert solution.isPowerOfTwo(0) == False      # zero is not a power of two
assert solution.isPowerOfTwo(-1) == False     # negative number
assert solution.isPowerOfTwo(-16) == False    # negative power-like value

assert solution.isPowerOfTwo(3) == False      # odd non-power
assert solution.isPowerOfTwo(6) == False      # even non-power
assert solution.isPowerOfTwo(12) == False     # multiple set bits
assert solution.isPowerOfTwo(218) == False    # random non-power

assert solution.isPowerOfTwo(2**30) == True   # large valid boundary case
assert solution.isPowerOfTwo(2**31 - 1) == False  # max int, not power of two

Test Summary

Test Why
1 Verifies 2^0 handling
2, 4, 16 Standard power-of-two cases
1024 Larger valid input
0 Ensures zero is rejected
Negative values Ensures only positive numbers pass
3, 6, 12 Non-power values with multiple set bits
2^30 Large valid power within constraints
2^31 - 1 Upper bound non-power case

Edge Cases

Zero Input

The value 0 is a common source of bugs. In binary, 0 & (-1) evaluates to 0, which could incorrectly suggest that zero is a power of two if we only use the bitwise condition. The implementation avoids this by first checking whether n <= 0.

Negative Numbers

Negative integers use two's complement binary representation. Because of this representation, some negative numbers can behave unexpectedly with bit operations. Since powers of two are mathematically positive, the implementation immediately rejects all non-positive inputs before performing the bit trick.

The Value One

Many developers forget that 1 is technically a power of two because:

$$1 = 2^0$$

The algorithm handles this correctly:

1 & 0 = 0

so the function properly returns true.

Numbers With Multiple Set Bits

Values such as 3, 5, or 12 contain multiple 1 bits in binary form. These are not powers of two. The bitwise AND operation leaves at least one set bit remaining, producing a nonzero result and correctly returning false.