LeetCode 342: Power of Four

Problem Restatement

We are given an integer n.

Return true if n is a power of four. Otherwise return false.

A number is a power of four if there exists an integer x such that:

n = 4^x

Examples:

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

are powers of four.

The official problem asks whether n is a power of four and includes a follow-up asking for a solution without loops or recursion. (leetcode.com)

Input and Output

Function shape:

def isPowerOfFour(n: int) -> bool:
    ...

Examples

Example 1:

Input: n = 16
Output: true

Because:

16 = 4^2

Example 2:

Input: n = 5
Output: false

There is no integer x such that:

4^x = 5

Example 3:

Input: n = 1
Output: true

Because:

1 = 4^0

First Thought: Repeated Division

A direct approach is:

1. While n is divisible by 4:
   1. Divide n by 4.
2. At the end, check whether n == 1.

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

        while n % 4 == 0:
            n //= 4

        return n == 1

This works, but the follow-up asks for a constant-time bit solution.

Key Insight

A power of four is also a power of two.

So first check whether n has exactly one set bit.

For powers of two:

n & (n - 1) == 0

Examples:

Subtracting 1 flips all bits after the single set bit.

Example:

8      = 1000
8 - 1  = 0111
AND    = 0000

But powers of two are not enough.

For example:

8 = 2^3

is not a power of four.

So we need another property.

Binary Pattern of Powers of Four

Powers of four have their single 1 bit at even bit positions.

Examples:

All are even positions.

The hexadecimal mask:

0x55555555

has binary form:

01010101010101010101010101010101

It keeps only even-position bits.

So a number is a power of four if:

1. n > 0
2. n is a power of two
3. Its set bit is in an even position

The third condition is:

n & 0x55555555 != 0

Algorithm

Return whether all three conditions hold:

n > 0
and n & (n - 1) == 0
and n & 0x55555555 != 0

Walkthrough

Use:

n = 16

Binary:

16 = 00010000

Check positivity:

16 > 0

true.

Check power of two:

16 & 15
00010000
00001111
--------
00000000

So 16 has exactly one set bit.

Check even-position mask:

16 & 0x55555555 != 0

The set bit survives because it is at position 4, which is even.

Return True.

Now use:

n = 8

Binary:

8 = 00001000

It passes the power-of-two check.

But its set bit is at position 3, which is odd.

So:

8 & 0x55555555 == 0

Return False.

Correctness

If the algorithm returns true, then:

1. n > 0
2. n & (n - 1) == 0
3. n & 0x55555555 != 0

The second condition means n has exactly one set bit, so n is a power of two.

The third condition means that set bit is located at an even bit position.

Powers of four are exactly the powers of two whose single set bit appears at positions:

0, 2, 4, 6, ...

Therefore n must equal:

4^x

for some nonnegative integer x.

Now suppose n is a power of four.

Then n is positive.

Its binary representation contains exactly one set bit, so:

n & (n - 1) == 0

Also, powers of four place that bit at an even position, so:

n & 0x55555555 != 0

Therefore all three conditions hold, and the algorithm returns true.

So the algorithm returns true exactly for powers of four.

Complexity

Implementation

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

Code Explanation

First check positivity:

n > 0

Negative numbers and zero cannot be powers of four.

Then check whether n is a power of two:

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

This ensures there is exactly one set bit.

Finally check whether that bit is in an even position:

(n & 0x55555555) != 0

The mask keeps only bits at positions:

0, 2, 4, 6, ...

If all conditions are true, n is a power of four.

Testing

def run_tests():
    s = Solution()

    assert s.isPowerOfFour(1) == True
    assert s.isPowerOfFour(4) == True
    assert s.isPowerOfFour(16) == True
    assert s.isPowerOfFour(64) == True

    assert s.isPowerOfFour(2) == False
    assert s.isPowerOfFour(8) == False
    assert s.isPowerOfFour(5) == False
    assert s.isPowerOfFour(0) == False
    assert s.isPowerOfFour(-4) == False

    print("all tests passed")

run_tests()

Test meaning: