LeetCode Problem 342

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

Solution

LeetCode 342 - Power of Four

Problem Understanding

This problem asks us to determine whether a given integer n is an exact power of four. In other words, we need to check whether there exists some integer x such that:

n = 4^x

Examples of powers of four are:

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

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

• Return true if n is a power of four.
• Return false otherwise.

The constraints allow values from:

-2^31 <= n <= 2^31 - 1

This means the input can be negative, zero, or positive. Since powers of four are always positive integers, any non-positive number immediately fails the condition.

An important detail is the follow-up question:

Could you solve it without loops/recursion?

This hint strongly suggests that the intended optimal solution uses mathematical or bit manipulation properties instead of repeatedly dividing by four.

Several edge cases are important:

• n <= 0

• Powers of four must be positive.

• Values like 0, -4, or -16 should return false.

• n = 1

• Since 1 = 4^0, the answer should be true.

• Powers of two that are not powers of four

• For example:

8  = 2^3
32 = 2^5

• These contain only one set bit, but they are not powers of four.

• Large values near the integer limit

• The solution should remain efficient and avoid overflow issues.

Approaches

Brute Force Approach

A straightforward solution is to repeatedly divide the number by 4 while it remains divisible by 4.

The logic works as follows:

1. If n <= 0, return false.
2. While n % 4 == 0, divide n by 4.
3. At the end:

• If n == 1, it was a power of four.
• Otherwise, it was not.

This approach is correct because every power of four can be reduced to 1 through repeated division by 4.

For example:

16 -> 4 -> 1
64 -> 16 -> 4 -> 1

If at any point the number is not divisible by 4, then it cannot be a power of four.

Although this solution is already efficient for the given constraints, the follow-up asks for a solution without loops or recursion.

Optimal Bit Manipulation Approach

The key insight is that every power of four has two special properties:

1. It is also a power of two.
2. Its single set bit appears only in an odd-numbered position.

Recall the binary representations:

1   = 0001
4   = 0100
16  = 00010000
64  = 01000000

Notice that:

• Each value has exactly one 1 bit.
• That bit always appears at positions:

0, 2, 4, 6, ...

To check whether a number is a power of two, we use:

n & (n - 1) == 0

This works because powers of two contain exactly one set bit.

However, powers of four are only a subset of powers of two. For example:

8  = 1000
32 = 100000

These are powers of two but not powers of four.

To distinguish them, we use the hexadecimal mask:

0x55555555

Its binary form is:

01010101010101010101010101010101

This mask keeps only bits in valid power-of-four positions.

So the final conditions are:

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

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

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(log₄ n)	O(1)	Repeatedly divides by 4
Optimal	O(1)	O(1)	Uses bit manipulation without loops

Algorithm Walkthrough

1. First, check whether n is positive.

Powers of four must be greater than zero. If n <= 0, immediately return false. 2. Check whether n is a power of two.

Use the expression:

n & (n - 1)

A power of two has exactly one set bit. Subtracting 1 flips all lower bits, so the AND operation becomes zero only for powers of two.

Examples:

16 = 10000
15 = 01111
AND = 00000

But:

12 = 01100
11 = 01011
AND = 01000

3. Verify that the set bit is in a valid power-of-four position.

Use the mask:

0x55555555

This mask contains 1s only in positions corresponding to powers of four.

Perform:

n & 0x55555555

If the result is nonzero, the bit lies in the correct position. 4. Return the combined result.

The number is a power of four only if all conditions are satisfied.

Why it works

The algorithm relies on two mathematical properties:

• Every power of four is also a power of two, meaning it contains exactly one set bit.
• The single set bit of a power of four always appears in an even-indexed binary position.

The first condition eliminates numbers with multiple set bits, and the second condition eliminates powers of two that are not powers of four. Together, they uniquely identify powers of four.

Python Solution

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

The implementation consists of three logical checks combined into a single return statement.

The first condition ensures the number is positive. This immediately removes invalid inputs such as zero and negative numbers.

The second condition checks whether the number is a power of two. The expression:

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

is a classic bit manipulation trick that works because powers of two contain exactly one set bit.

The third condition uses the mask 0x55555555 to verify that the set bit appears in a valid power-of-four position. Without this step, values like 8 or 32 would incorrectly pass.

All checks are constant time operations, making the solution extremely efficient.

Go Solution

func isPowerOfFour(n int) bool {
	return n > 0 &&
		(n&(n-1)) == 0 &&
		(n&0x55555555) != 0
}

The Go implementation is nearly identical to the Python version because both languages support bitwise operations directly.

One small difference is that Go uses explicit integer operators without automatic boolean chaining syntax differences. The logic itself remains unchanged.

The constant 0x55555555 safely fits within Go's integer range on standard LeetCode environments.

Worked Examples

Example 1

Input:

n = 16

Binary representation:

10000

Step	Expression	Result
Positive check	16 > 0	true
Power of two check	16 & 15	0
Mask check	16 & 0x55555555	nonzero
Final result	all conditions true	true

Output:

true

Example 2

Input:

n = 5

Binary representation:

00101

Step	Expression	Result
Positive check	5 > 0	true
Power of two check	5 & 4	4
Final result	not a power of two	false

Output:

false

Example 3

Input:

n = 1

Binary representation:

0001

Step	Expression	Result
Positive check	1 > 0	true
Power of two check	1 & 0	0
Mask check	1 & 0x55555555	nonzero
Final result	all conditions true	true

Output:

true

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Uses a fixed number of bit operations
Space	O(1)	No additional data structures are used

The algorithm performs only a few arithmetic and bitwise operations regardless of input size. Since the number of operations never changes, the runtime is constant.

The space usage is also constant because the solution stores only a few temporary values and does not allocate extra memory proportional to the input.

Test Cases

solution = Solution()

assert solution.isPowerOfFour(16) == True      # standard power of four
assert solution.isPowerOfFour(5) == False      # not a power of four
assert solution.isPowerOfFour(1) == True       # 4^0

assert solution.isPowerOfFour(4) == True       # smallest nontrivial power of four
assert solution.isPowerOfFour(64) == True      # larger power of four
assert solution.isPowerOfFour(256) == True     # another valid power

assert solution.isPowerOfFour(8) == False      # power of two but not four
assert solution.isPowerOfFour(32) == False     # another power of two only
assert solution.isPowerOfFour(12) == False     # multiple set bits

assert solution.isPowerOfFour(0) == False      # zero is invalid
assert solution.isPowerOfFour(-4) == False     # negative number
assert solution.isPowerOfFour(-64) == False    # larger negative number

assert solution.isPowerOfFour(2) == False      # smallest power of two only
assert solution.isPowerOfFour(3) == False      # small non-power
assert solution.isPowerOfFour(1024) == True    # 4^5

assert solution.isPowerOfFour(2147483647) == False  # max 32-bit signed int

Test	Why
16	Standard positive example
5	Non-power value
1	Valid because 1 = 4^0
4	Smallest positive power of four after 1
64	Larger valid power
256	Verifies repeated power scaling
8	Power of two but not four
32	Another incorrect power of two
12	Multiple set bits
0	Non-positive edge case
-4	Negative number
-64	Larger negative input
2	Smallest invalid power of two
3	Small non-power value
1024	Larger valid input
2147483647	Maximum signed 32-bit integer

Edge Cases

One important edge case is when the input is zero or negative. Powers of four are strictly positive because every exponentiation of four produces a positive result. A naive implementation that only checks divisibility or bit patterns could accidentally mishandle negative values. The implementation prevents this by immediately requiring n > 0.

Another important case is n = 1. Many implementations forget that 1 is a valid power of four because:

1 = 4^0

The bit manipulation approach correctly handles this case because 1 contains exactly one set bit, and that bit lies in a valid power-of-four position.

A third critical edge case involves numbers that are powers of two but not powers of four, such as 8 or 32. These values pass the classic power-of-two check:

n & (n - 1) == 0

Without the additional mask check, they would incorrectly return true. The mask 0x55555555 ensures the single set bit appears only in allowed positions, which correctly rejects these values.