How do you solve Power of Four on LeetCode?

Power of Four (LeetCode #342) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(1) time complexity and O(1) space complexity. Key insight: A number must be positive to be a power of four.

What is the time complexity of Power of Four?

The optimal solution for Power of Four runs in O(1) time and uses O(1) space. The time complexity is O(1) because we are performing a constant number of operations regardless of the input size.

What is the brute force solution for Power of Four?

The brute force approach for Power of Four is Brute Force, with O(log n) time complexity and O(1) space complexity. We can repeatedly divide the number by 4 until we reach 1 or a number less than 1. If we reach 1, it means the original number was a power of four. The optimal Optimal Solution approach improves this to O(1).

What algorithm or data structure is used to solve Power of Four?

Power of Four uses the following concepts: Math, Bit Manipulation, Recursion. The recommended patterns to study are: Bit Manipulation, Mathematical Properties.

What are the interview tips for Power of Four?

Always consider edge cases, such as negative numbers and zero. Explain your thought process clearly; it helps the interviewer follow your logic. If asked for an optimal solution, think about mathematical properties or bit manipulation.

What are common mistakes when solving Power of Four?

Forgetting to check if n is greater than 0. Confusing powers of two with powers of four.

#342

Power of Four

Easy

MathBit ManipulationRecursionBit ManipulationMathematical Properties

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(log n)	O(1)
Space	O(1)	O(1)

💡

Intuition

Time O(1)Space O(1)

We can use a mathematical property of powers of four. A number is a power of four if it is a power of two and the exponent is even. We can check this using bit manipulation.

⚙️

Algorithm

3 steps

1Step 1: Check if n is greater than 0.
2Step 2: Check if n is a power of two by ensuring only one bit is set (n & (n - 1) == 0).
3Step 3: Check if the set bit is in the correct position for powers of four using (n - 1) % 3 == 0.

solution.py2 lines

1def isPowerOfFour(n):
2    return n > 0 and (n & (n - 1)) == 0 and (n - 1) % 3 == 0

ℹ

Complexity note: The time complexity is O(1) because we are performing a constant number of operations regardless of the input size.

1A number must be positive to be a power of four.
2Using bit manipulation can simplify checks for powers of two.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.