1131EasyMathBit ManipulationRecursion

Is the Number a Power of Four

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Return true when the whole number n is a power of four, meaning n equals 4 raised to some whole power of zero or more.

Examples

Example 1

Input: n = 64
Output: true

Four multiplied by itself three times comes to 64.

Example 2

Input: n = 8
Output: false

Eight is a power of two but not of four: dividing it by four leaves two behind.

Example 3

Input: n = 0
Output: false

Every power of four is at least one, so nothing this small qualifies.

Constraints

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

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def is_power_of_four(n: int) -> bool:

Java

public boolean isPowerOfFour(int n)

The intended approach

Time O(1).Space O(1).

A power of four is a power of two whose single bit sits at an even place, counting the lowest as place zero. So the test splits in three parts, each cheap. First, the number has to be positive, which rules out zero and everything below it. Second, it has to carry exactly one bit, which is what subtracting one and combining with AND detects: for a lone bit the subtraction flips it off and turns everything beneath it on, so the two share nothing. Third, that bit has to sit at an even place, and the remainder against three settles it without any shifting. Four leaves one against three, so four to any power leaves one as well, while two times a power of four leaves two. So a lone-bit number leaves one against three exactly when its bit sits at an even place, and one itself, being four to the power of nothing, passes all three parts.

Pythonentry point: is_power_of_four

def is_power_of_four(n):
    if n <= 0:
        return False
    if n & (n - 1):
        return False
    return n % 3 == 1

The obvious version

Divide the number by four for as long as it divides exactly, then check that what is left is one. Anything that is not positive fails outright. Costs one division per digit place.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_is_power_of_four(n):
    if n <= 0:
        return False
    while n % 4 == 0:
        n //= 4
    return n == 1

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in