Power of Four

Start by checking if the number is positive and a power of two, since all powers of four are powers of two. Then use bit manipulation to ensure the single set bit is in the correct position for a power of four. Recursive or mathematical verification can also confirm validity, making the solution concise and interview-ready for this math plus bit manipulation pattern.

Problem Statement

Given an integer n, return true if n is a power of four, and false otherwise. A power of four is defined as n equal to 4 raised to some integer exponent x.

You must implement an efficient solution leveraging both mathematical checks and bit manipulation. Example scenarios include n = 16 returning true, n = 5 returning false, and n = 1 returning true. Constraints: -231 <= n <= 231 - 1.

Examples

Example 1

Input: n = 16

Output: true

Example details omitted.

Example 2

Input: n = 5

Output: false

Example details omitted.

Example 3

Input: n = 1

Output: true

Example details omitted.

Constraints

• -231 <= n <= 231 - 1

Solution Approach

Bit Masking Verification

Check if n > 0 and n is a power of two using n & (n - 1) == 0. Then ensure the set bit is at an even position, which confirms it is a power of four. This approach directly ties the bit pattern to the mathematical property of powers of four.

Mathematical Division

Repeatedly divide n by 4 while it is divisible. If the final result is 1, then n is a power of four. This method emphasizes the math pattern and avoids unnecessary bit-level operations, highlighting the simplicity of division-based verification.

Recursive Check

Use recursion to divide n by 4 and verify each step until reaching 1. Return false if any division step leaves a remainder. This approach combines the mathematical understanding of powers with the recursive pattern, reflecting a common interview exploration of this problem.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity ranges from O(1) for bit manipulation to O(log n) for division or recursion. Space complexity is O(1) for iterative solutions and O(log n) for recursion due to call stack usage.

What Interviewers Usually Probe

• Ask about distinguishing power of two versus power of four with bit operations.
• Probe candidate understanding of position of the set bit in powers of four.
• Expect efficient solutions rather than brute force iterations or floating-point checks.

Common Pitfalls or Variants

Common pitfalls

• Checking only n > 0 or n & (n - 1) without verifying bit position can misidentify powers of two as powers of four.
• Using floating-point logarithms may introduce precision errors in edge cases.
• Failing to handle n = 1 correctly, which is a valid power of four (4^0).

Follow-up variants

• Power of Two check without enforcing power of four constraints.
• Power of Eight verification requiring similar bit and math insights.
• Recursive-only solution without bit manipulation optimizations.

FAQ

How can I quickly check if a number is a power of four?

Use bit manipulation: confirm n > 0, n & (n - 1) == 0, and the set bit is at an even position.

Can recursion be used efficiently for Power of Four?

Yes, recursively divide by 4 until reaching 1 or encountering a remainder, reflecting the math pattern.

What common mistakes occur in Power of Four checks?

Misidentifying powers of two as powers of four or relying on floating-point logarithms can cause incorrect results.

Is there a purely mathematical approach without bit operations?

Repeatedly divide n by 4 and check if the final result is 1. This avoids bit manipulation entirely.

Why is bit position important in the Power of Four problem?

Because only powers of four have their single set bit at even positions, ensuring correct distinction from other powers of two.