Check if a Number is a Power of 4

Problem Statement

Given an integer n, check whether it is a power of 4. A number is considered a power of 4 if it can be written as 4^k where k is a non-negative integer.

Input:

• An integer n (0 ≤ n ≤ 2^31 - 1)

Output:

• Returns true if the number is a power of 4
• Returns false otherwise

Examples

Example 1:

Input: n = 16
Output: true

Explanation: 16 = 4^2

Example 2:

Input: n = 8
Output: false

Explanation: 8 = 2^3, not a power of 4

Example 3:

Input: n = 1
Output: true

Explanation: 1 = 4^0

Different Approaches

1️⃣ Iterative Division

Intuition:

Keep dividing n by 4 until you reach 1. If at any point it’s not divisible by 4, return false.

Approach:

• If n <= 0, return false.
• While n % 4 == 0, divide n by 4.
• After the loop, check if n == 1.

Dry Run:

n = 16

16 % 4 == 0 → divide → n = 4
4 % 4 == 0 → divide → n = 1
✅ n == 1 → it's a power of 4

n = 8

8 % 4 == 0 -> divide -> n = 2
2 % 4 != 0 -> loop ends
❌ n != 1 → not a power of 4

Code:

#include <iostream>

using namespace std;

bool isPowerOfFour(int n) {
    if (n <= 0) return false; // negative numbers and 0 are not powers of 4
    
    while (n % 4 == 0) {
        n /= 4;
    }

    return n == 1;
}

int main()
{
    cout << isPowerOfFour(16);
}

Complexity Analysis:

• Time Complexity:O(log4 (n)), logarithmic in base 4.
  • As we are dividing by 4.
• Space Complexity:O(1)
  • No extra space is required.

2️⃣ Bit Manipulation

Intuition:

• A power of 4 is a power of 2 → only one bit set.
• The position of the bit should be even (e.g., 1st, 3rd, 5th…).

Approach:

1. Check n > 0
2. Check if n is power of 2: n & (n - 1) == 0
3. Ensure the only set bit is at an even position: (n & 0x55555555) != 0

0x55555555 in binary: 01010101010101010101010101010101
This masks the even bits.

Let's take an example:

n = 16, Binary = 0001 0000

Position: 7 6 5 4 3 2 1 0
n       : 0 0 0 1 0 0 0 0

Mask (0x55 -> 0101 0101)
Position: 7 6 5 4 3 2 1 0
mask    : 0 1 0 1 0 1 0 1

Bitwise AND:
Position: 7 6 5 4 3 2 1 0
Result  : 0 0 0 1 0 0 0 0

Result != 0 -> Bit is at even position
Since n is a power of 2 and the bits is in
even position 16 is a power of 4.

n = 5, Binary = 0000 0101

Position: 7 6 5 4 3 2 1 0
n       : 0 0 0 0 0 1 0 1

Mask (0x55 -> 0101 0101)
Position: 7 6 5 4 3 2 1 0
mask    : 0 1 0 1 0 1 0 1

Bitwise AND:
Position: 7 6 5 4 3 2 1 0
Result  : 0 0 0 0 0 1 0 1

Result != 0 (in fact, it's 5)
But n = 5 is not a power of 2 (since more than
one bit is set), So it is not a power of 4.

Code:

#include <iostream>

using namespace std;

bool isPowerOfFour(int n) {
    return n > 0 &&
           (n & (n - 1)) == 0 &&
           (n & 0x55555555);
}


int main()
{
    cout << isPowerOfFour(8);
}

Complexity Analysis:

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

3️⃣ Modulus Approach

Intuition:

A number n is a power of 4if and only if:

1. n is a power of 2 → only one bit is set.
2. n % 3 == 1 → mathematical property true only for powers of 4.

Why Does n % 3 == 1 Work?

Let's look at a few powers:

so for powers of 2 that are not powers of 4, n % 3 ≠ 1.

Code:

#include <iostream>

using namespace std;

bool isPowerOfFour(int n) {
    return n > 0 &&
           (n & (n - 1)) == 0 &&  // Power of 2
           (n % 3 == 1);          // Only powers of 4 give remainder 1
}


int main()
{
    cout << isPowerOfFour(8);
}

Complexity Analysis:

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