Power of Four

How it works

Powers of four follow a pattern when divided by 3: 4^k mod 3 = 1 for all non-negative k. This is because 4 = 3 + 1, so 4^k = (3+1)^k, which when expanded always leaves remainder 1.

Powers of two that are not powers of four (like 2, 8, 32) give remainder 2 when divided by 3. This gives us a simple way to distinguish between them.

Steps

1. Check that n is positive.
2. Check that n is a power of two: (n & (n - 1)) == 0.
3. Check that n % 3 == 1 to confirm it's specifically a power of four.
4. Return true if all conditions are met.

Complexity

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

Things to watch for

Confusing Power of Two with Power of Four

All powers of four are powers of two, but not vice versa. Checking only (n & (n - 1)) == 0 accepts values like 2, 8, and 32 which are powers of two but not four. You must add an additional check to verify the set bit is at an even position.

Floating-Point Precision Errors with Logarithms

Using log(n) / log(4) can introduce floating-point errors. For example, log(64) / log(4) might return 2.9999999... instead of exactly 3. Comparing with == 0 after modulo may incorrectly reject valid powers of four. Consider rounding or using integer-based approaches instead.

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

class Solution {
public:
    bool isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && (n % 3 == 1);
    }
};