Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The powers of four form a strictly increasing sequence: 1, 4, 16, .... Once a generated power exceeds the input, every later power will also be too large. This lets us test membership directly without floating-point logarithms.

Approach

Start the candidate at one, which represents 4^0.
While the candidate is at most n, return true if they match; otherwise multiply the candidate by four.
Return false when the candidate passes n. Zero and negative inputs skip the loop and are rejected, while one is accepted immediately.

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        curr = 1

        while curr <= n:
            if curr == n:
                return True
            curr *= 4

        return False

Complexity analysis

For n > 1, generating successive powers of four takes O(log_4 n) time. Inputs n <= 1 take O(1) time: one is accepted immediately, while zero and negative inputs skip the loop. Auxiliary space is O(1) under the 32-bit input constraint.