DSA SheetEasy
EditorialPractice

RECURSION & BACKTRACKING › RECURSION PROBLEMS

Power of Four

EasyEditorial · 6 minGenerated by gpt-5.6-luna · Aug 26

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitionwhy one bit position identifies every power of four

The powers of four are 1, 4, 16, 64, and so on. In binary, each multiplication by four shifts the only set bit left by two positions: 1 is 1, 4 is 100, 16 is 10000, and 64 is 1000000. Therefore, the answer is determined by two facts: there must be exactly one set bit, and its zero-based position must be even.

The expression n & (n - 1) removes the lowest set bit. It becomes zero exactly when n has one set bit, which recognizes every positive power of two. To separate powers of four from powers of two such as 2, 8, and 32, inspect the bit positions with odd indices. The mask 0xaaaaaaaa has ones at positions 1, 3, 5, and so on, so a valid power of four must have no overlap with it.

Approach

  1. Reject n <= 0, because powers of four are positive and the bit tests alone could otherwise treat an invalid value incorrectly.
  2. Check (n & (n - 1)) == 0, because a power of four must contain exactly one set bit; this also removes values with several set bits such as 5.
  3. Check (n & 0xaaaaaaaa) == 0, because the mask covers every odd bit position and a power of four places its only set bit at an even position.
  4. Return true only when all three conditions hold, so values such as 16 pass while 2 and 5 fail for different reasons.

Complexityconstant work on a fixed-width integer

MEASUREBOUNDWHY
TimeO(1)The solution performs a fixed number of integer comparisons and bitwise operations. A 32-bit integer has a fixed representation, so no loop scans an input-dependent number of bits.
SpaceO(1)Only the input and a fixed number of temporary values are used. The boolean result is required output and is excluded from the extra-space bound; the bound stays constant for every allowed input shape.

Annotated solutionC++ · bit checks · the three conditions mirror the definition

CPPChecks positivity, a single set bit, and an even bit position.
#include <cstdint>

using namespace std;

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

The order of the conditions makes the reasoning easy to audit. Positivity removes zero and negatives before they reach the bit logic. The n & (n - 1) test proves that exactly one bit is set. Once that is known, the mask test only needs to decide whether that one bit is in an odd position; no loop or conversion to a string is necessary.

The divisibility alternativea different test for the same even exponent

You can replace the position mask with modular arithmetic. First confirm that n is a positive power of two. Powers of two alternate modulo 3: 2 has remainder 2, 4 has remainder 1, 8 has remainder 2, and 16 has remainder 1. Thus a positive power of two is a power of four exactly when n % 3 equals 1, or equivalently when n - 1 is divisible by 3.

CPPUses modulo 3 to distinguish even and odd powers of two.
#include <cstdint>

using namespace std;

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

This is not an asymptotic optimization: both versions use constant time and constant extra space. The mask version exposes the exact bit-position rule and avoids arithmetic reasoning. The modulo version is shorter conceptually once you know the alternating remainders, but the mask is often easier to generalize when a problem asks about particular bit positions.

Common mistakesthe two checks that are easiest to omit

Previous · Power of Three