LeetCode 231: Power of Two

Problem Restatement

We are given an integer n.

We need to determine whether n is a power of two.

That means we must check whether there exists an integer x such that:

where:

x >= 0

Examples of powers of two:

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

Examples that are not powers of two:

3
5
6
12
18

LeetCode examples include:

Input:  n = 1
Output: true

Input:  n = 16
Output: true

Input:  n = 3
Output: false

The constraints allow signed 32-bit integers. (leetcode.com)

Input and Output

Function shape:

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        ...

Examples

Example 1:

Input:  n = 1
Output: true

Because:

Example 2:

Input:  n = 16
Output: true

Because:

Example 3:

Input:  n = 3
Output: false

Because no integer x satisfies:

Example 4:

Input:  n = 0
Output: false

Zero is not a power of two.

Example 5:

Input:  n = -8
Output: false

Negative numbers are not powers of two.

First Thought: Repeated Division

One direct approach is:

1. If n <= 0, return False.
2. While n is divisible by 2, divide it by 2.
3. If we finally reach 1, return True.
4. Otherwise, return False.

Example:

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

This works because every power of two can be repeatedly divided by two until reaching one.

Implementation:

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

        while n % 2 == 0:
            n //= 2

        return n == 1

This solution is correct, but there is an even cleaner bit manipulation approach.

Key Insight

A power of two has exactly one 1 bit in binary representation.

Examples:

1   = 0001
2   = 0010
4   = 0100
8   = 1000
16  = 10000

Every power of two contains:

exactly one set bit

Now consider subtracting one.

Example:

8      = 1000
8 - 1  = 0111

Another:

16      = 10000
16 - 1  = 01111

A power of two and one less than itself never share a 1 bit.

So:

for every positive power of two.

Binary Visualization

Take:

n = 8

Binary:

1000

Now subtract one:

0111

Bitwise AND:

1000
0111
----
0000

Result:

0

Now try a number that is not a power of two:

n = 10

Binary:

1010

Subtract one:

1001

AND:

1010
1001
----
1000

Result is not zero.

So 10 is not a power of two.

Algorithm

1. If n <= 0, return False.
2. Compute:

3. If the result is zero, return True.
4. Otherwise, return False.

Correctness

Suppose n is a positive power of two.

Then its binary representation contains exactly one set bit.

For example:

1000

Subtracting one flips that bit to 0 and turns all lower bits into 1:

0111

The two numbers share no set bits.

Therefore:

Now suppose n is positive but not a power of two.

Then its binary representation contains at least two set bits.

Subtracting one removes only the lowest set bit, so at least one set bit remains shared between n and n - 1.

Therefore:

Finally, numbers less than or equal to zero are never powers of two.

Therefore, the algorithm returns True exactly for positive powers of two.

Complexity

Implementation

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

Code Explanation

First we check:

n > 0

because zero and negative numbers are invalid.

Then we use the binary property:

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

A positive integer satisfying this condition has exactly one set bit.

That means the number is a power of two.

Alternative Approach: Count Bits

Another method is to count how many 1 bits appear in the binary representation.

A power of two has exactly one set bit.

Example:

8  = 1000   -> one set bit
10 = 1010   -> two set bits

Python solution:

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and bin(n).count("1") == 1

This is simpler conceptually, but slower and less elegant than direct bit manipulation.

Testing

def run_tests():
    s = Solution()

    assert s.isPowerOfTwo(1) is True
    assert s.isPowerOfTwo(2) is True
    assert s.isPowerOfTwo(4) is True
    assert s.isPowerOfTwo(16) is True
    assert s.isPowerOfTwo(1024) is True

    assert s.isPowerOfTwo(0) is False
    assert s.isPowerOfTwo(3) is False
    assert s.isPowerOfTwo(6) is False
    assert s.isPowerOfTwo(10) is False
    assert s.isPowerOfTwo(-8) is False

    print("all tests passed")

run_tests()