Log inSign up
easyLeetCodeNot Started

Power of Four

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on LeetCode
Lesson

Problem Statement

Given an integer n, return true if it is a power of four. Otherwise, return false.

An integer n is a power of four if there exists an integer x such that n == 4^x.

Could you solve it without loops or recursion in O(1) time?

Example 1 · Example 1: Positive Power of Four:

Input: n = 16
Output: true
Explanation: 16 = 42.

Example 2 · Example 2: Power of Two but Not Four:

Input: n = 8
Output: false
Explanation: 8 = 23, which is not an integer power of 4.

Example 3 · Example 3: Boundary Case 1:

Input: n = 1
Output: true
Explanation: 1 = 40.

Constraints:

  • -231 <= n <= 231 - 1

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Distinguish powers of 4 from general powers of 2 using bit parity.
  • Understand the hex bitmask 0x55555555 corresponding to even-indexed bits.
  • Apply modulo-3 algebraic number theory proofs to powers of 4.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Check if n is 4x without loops or recursion.
  • Filtering specific power-of-two exponent parities.
  • Bitmask classification.

Algorithmic Decision Tree:

  • Check n > 0.
  • Check (n & (n - 1)) == 0.
  • Check (n & 0x55555555) != 0.

Connected Patterns:

Power of TwoNumber of 1 BitsFind Position of Rightmost Set Bit

1. Repeated Division by 4

Intuition

If n <= 0, return false. While n % 4 == 0, divide n /= 4. Return n == 1.

When to apply: Basic definition.

Algorithm

  1. Step 1: If n <= 0, return false.
  2. Step 2: While n % 4 == 0, n /= 4.
  3. Step 3: Return n == 1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5bool isPowerOfFourBrute(int n) {
6 if (n <= 0) return false;
7 while (n % 4 == 0) {
8 n /= 4;
9 }
10 return n == 1;
11}
12
13int main() {
14 cout << boolalpha;
15 cout << "Brute (16): " << isPowerOfFourBrute(16) << endl; // true
16 cout << "Brute (8): " << isPowerOfFourBrute(8) << endl; // false
17 cout << "Brute (1): " << isPowerOfFourBrute(1) << endl; // true
18 return 0;
19}

Time & Space Complexity

  • Time complexity: O(log4 n)
  • Space complexity: O(1)

2. Power of Two & Modulo 3

Intuition

Powers of two have form 2^k. If k is even (k = 2x), 2^(2x) = 4^x = (3 + 1)^x = 1 mod 3. If k is odd (k = 2x + 1), 2^(2x + 1) = 2 * 4^x = 2 mod 3. Therefore, testing n % 3 == 1 uniquely isolates powers of four.

When to apply: When hex constants are undesirable.

Algorithm

  1. Step 1: Check n > 0.
  2. Step 2: Check (n & (n - 1)) == 0.
  3. Step 3: Check n % 3 == 1.
  4. Step 4: Return true if all pass.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5bool isPowerOfFourMod3(int n) {
6 return n > 0 && (n & (n - 1)) == 0 && (n % 3 == 1);
7}
8
9int main() {
10 cout << boolalpha;
11 cout << "Mod3 (16): " << isPowerOfFourMod3(16) << endl; // true
12 cout << "Mod3 (8): " << isPowerOfFourMod3(8) << endl; // false
13 return 0;
14}

Time & Space Complexity

  • Time complexity: O(1)
  • Space complexity: O(1)

3. Direct Even Bitmask (0x55555555)

Intuition

Verify that n > 0, that n is a power of two (n & (n - 1)) == 0, and that its solitary set bit is positioned at an even bit index via the mask 0x55555555.

When to apply: Optimal canonical bitwise solution for Power of Four.

Algorithm

  1. Step 1: Return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0.

Bitmask Validation Trace for n = 16 and n = 8

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Case 1 (n = 16): 16 > 0 (true)
Visual state
Values and pointers at this exact step
pointers
S
even bit
0
↑ true
Check / comparison
16 & 0x55555555 != 0
Decision / next transition
Result: true.
Why this step matters

Case 1 (n = 16): 16 > 0 (true). 16 & 15 == 0 (true power of 2). 16 & 0x55555555 = 16 != 0 (bit 4 is even). Valid power of 4.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class Solution {
6public:
7 bool isPowerOfFour(int n) {
8 return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0;
9 }
10};
11
12int main() {
13 Solution sol;
14 cout << boolalpha;
15 cout << "Optimal (16): " << sol.isPowerOfFour(16) << endl; // true
16 cout << "Optimal (8): " << sol.isPowerOfFour(8) << endl; // false
17 cout << "Optimal (1): " << sol.isPowerOfFour(1) << endl; // true
18 cout << "Optimal (0): " << sol.isPowerOfFour(0) << endl; // false
19 return 0;
20}

Time & Space Complexity

  • Time complexity: O(1)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Repeated DivisionO(log4 n)O(1)While n > 0 and n % 4 == 0, n /= 4. Return n == 1.Iterative division.
2.Better — Power of Two & Modulo 3O(1)O(1)n > 0 && (n & (n - 1)) == 0 && (n % 3 == 1).Division/modulo instruction.
3.Optimal — Direct Even Bitmask (0x55555555)OptimalO(1)O(1)n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0.Single bitwise AND.

Common Pitfalls & Crucial Edge Cases

Assuming `n % 4 == 0` is sufficient

8 % 4 == 0 and 12 % 4 == 0, but neither is a power of 4.

Forgetting operator precedence

(n & (n - 1)) == 0 and (n & 0x55555555) != 0 require strict parentheses.

Using loop division

While while (n > 0 && n % 4 == 0) n /= 4 works, interviewers specifically request O(1) bit manipulation without loops.

Crucial Edge Cases to Validate:

  • n <= 0 — Powers of four are strictly positive; return false.
  • n = 1 (4^0) — Returns true.
  • Powers of two that are NOT powers of four (e.g. n = 2, 8, 32) — Returns false.
  • n = 2^30 (4^15) — Largest 32-bit power of four; returns true.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Present the three conditions: (1) n > 0, (2) (n & (n - 1)) == 0 (power of 2), (3) (n & 0x55555555) != 0 (even bit position).
  2. Mention the mathematical modulo 3 alternative: n > 0 && (n & (n - 1)) == 0 && (n - 1) % 3 == 0.
  3. Emphasize the strict O(1) time and O(1) auxiliary space execution.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What conditions must an integer n satisfy to be a power of four?

2.Why does masking with 0x55555555 verify that the set bit is at an even position?

3.What alternative mathematical property distinguishes powers of four from other powers of two?

Back to DSA Sheet