342. Power of Four - Explanation

Prerequisites

Before attempting this problem, you should be comfortable with:

Bit Manipulation - Understanding binary representation, bitwise AND, and how powers of two appear in binary
Logarithms - Using logarithms to determine exponents and checking for integer results
Power of Two Detection - The trick that n & (n-1) == 0 identifies powers of two

1. Recursion

Intuition

A number is a power of four if we can repeatedly divide it by 4 until we reach 1. If at any point the number is not divisible by 4 (or becomes zero or negative), it cannot be a power of four.

This naturally leads to a recursive solution where we reduce the problem size by dividing by 4 at each step.

Algorithm

If n equals 1, return true (4^0 = 1).
If n is less than or equal to 0, or n is not divisible by 4, return false.
Recursively check if n / 4 is a power of four.

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        if n == 1:
            return True
        if n <= 0 or n % 4:
            return False
        return self.isPowerOfFour(n // 4)

public class Solution {
    public boolean isPowerOfFour(int n) {
        if (n == 1) {
            return true;
        }
        if (n <= 0 || n % 4 != 0) {
            return false;
        }
        return isPowerOfFour(n / 4);
    }
}

class Solution {
public:
    bool isPowerOfFour(int n) {
        if (n == 1) {
            return true;
        }
        if (n <= 0 || n % 4 != 0) {
            return false;
        }
        return isPowerOfFour(n / 4);
    }
};

class Solution {
    /**
     * @param {number} n
     * @return {boolean}
     */
    isPowerOfFour(n) {
        if (n === 1) {
            return true;
        }
        if (n <= 0 || n % 4 !== 0) {
            return false;
        }
        return this.isPowerOfFour(Math.floor(n / 4));
    }
}

public class Solution {
    public bool IsPowerOfFour(int n) {
        if (n == 1) {
            return true;
        }
        if (n <= 0 || n % 4 != 0) {
            return false;
        }
        return IsPowerOfFour(n / 4);
    }
}

class Solution {
    fun isPowerOfFour(n: Int): Boolean {
        if (n == 1) {
            return true
        }
        if (n <= 0 || n % 4 != 0) {
            return false
        }
        return isPowerOfFour(n / 4)
    }
}

class Solution {
    func isPowerOfFour(_ n: Int) -> Bool {
        if n == 1 {
            return true
        }
        if n <= 0 || n % 4 != 0 {
            return false
        }
        return isPowerOfFour(n / 4)
    }
}

Time & Space Complexity

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

2. Iteration

Intuition

The same logic as recursion applies here, but we use a loop instead. We keep dividing n by 4 as long as it remains divisible. If we end up with 1, the original number was a power of four.

Algorithm

If n is negative, return false.
While n is greater than 1:
- If n is not divisible by 4, return false.
- Divide n by 4.
Return true if n equals 1, false otherwise.

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        if n < 0:
            return False

        while n > 1:
            if n % 4:
                return False
            n //= 4

        return n == 1

public class Solution {
    public boolean isPowerOfFour(int n) {
        if (n < 0) return false;

        while (n > 1) {
            if (n % 4 != 0) return false;
            n /= 4;
        }

        return n == 1;
    }
}

class Solution {
public:
    bool isPowerOfFour(int n) {
        if (n < 0) return false;

        while (n > 1) {
            if (n % 4 != 0) return false;
            n /= 4;
        }

        return n == 1;
    }
};

class Solution {
    /**
     * @param {number} n
     * @return {boolean}
     */
    isPowerOfFour(n) {
        if (n < 0) return false;

        while (n > 1) {
            if (n % 4 !== 0) return false;
            n = Math.floor(n / 4);
        }

        return n === 1;
    }
}

public class Solution {
    public bool IsPowerOfFour(int n) {
        if (n < 0) return false;

        while (n > 1) {
            if (n % 4 != 0) return false;
            n /= 4;
        }

        return n == 1;
    }
}

class Solution {
    fun isPowerOfFour(n: Int): Boolean {
        if (n < 0) return false

        var num = n
        while (num > 1) {
            if (num % 4 != 0) return false
            num /= 4
        }

        return num == 1
    }
}

class Solution {
    func isPowerOfFour(_ n: Int) -> Bool {
        if n < 0 {
            return false
        }

        var num = n
        while num > 1 {
            if num % 4 != 0 {
                return false
            }
            num /= 4
        }

        return num == 1
    }
}

Time & Space Complexity

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

3. Math

Intuition

If n is a power of 4, then n = 4^k for some integer k. Taking the logarithm base 4 of both sides gives k = log4(n). If this result is an integer, then n is a power of four.

We check if the logarithm yields a whole number by verifying the remainder when divided by 1 is zero.

Algorithm

If n is less than or equal to 0, return false.
Compute log(n) / log(4) to get the base-4 logarithm.
Return true if this value has no fractional part (i.e., modulo 1 equals 0).

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        return n > 0 and log(n, 4) % 1 == 0

Time & Space Complexity

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

4. Bit Manipulation

Intuition

Powers of four in binary are 1, 100, 10000, 1000000, etc. They have exactly one set bit, and that bit is always at an even position (0, 2, 4, ...).

We can check all even bit positions (0, 2, 4, ..., 30) and see if n equals exactly one of these values: 1, 4, 16, 64, and so on.

Algorithm

If n is negative, return false.
Iterate through even bit positions from 0 to 30 (step by 2):
- If n equals 1 << i (which is 4^(i/2)), return true.
If no match is found, return false.

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        if n < 0:
            return False

        for i in range(0, 32, 2):
            if n == (1 << i):
                return True

        return False

public class Solution {
    public boolean isPowerOfFour(int n) {
        if (n < 0) return false;

        for (int i = 0; i < 32; i += 2) {
            if (n == (1 << i)) {
                return true;
            }
        }

        return false;
    }
}

class Solution {
public:
    bool isPowerOfFour(int n) {
        if (n < 0) return false;

        for (int i = 0; i < 32; i += 2) {
            if (n == (1 << i)) {
                return true;
            }
        }

        return false;
    }
};

class Solution {
    /**
     * @param {number} n
     * @return {boolean}
     */
    isPowerOfFour(n) {
        if (n < 0) return false;

        for (let i = 0; i < 32; i += 2) {
            if (n === 1 << i) {
                return true;
            }
        }

        return false;
    }
}

public class Solution {
    public bool IsPowerOfFour(int n) {
        if (n < 0) return false;

        for (int i = 0; i < 32; i += 2) {
            if (n == (1 << i)) {
                return true;
            }
        }

        return false;
    }
}

class Solution {
    fun isPowerOfFour(n: Int): Boolean {
        if (n < 0) return false

        for (i in 0 until 32 step 2) {
            if (n == (1 shl i)) {
                return true
            }
        }

        return false
    }
}

class Solution {
    func isPowerOfFour(_ n: Int) -> Bool {
        if n < 0 {
            return false
        }

        for i in stride(from: 0, to: 32, by: 2) {
            if n == (1 << i) {
                return true
            }
        }

        return false
    }
}

Time & Space Complexity

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

5. Bit Mask - I

Intuition

A power of four must first be a power of two (exactly one bit set). We verify this using n & (n - 1) == 0. But not all powers of two are powers of four (e.g., 2 and 8 are not).

Powers of four have their single set bit at even positions. The mask 0x55555555 (binary: 01010101...) has 1s at all even positions. ANDing with this mask confirms the bit is at a valid position.

Algorithm

Check that n is positive.
Check that n is a power of two: (n & (n - 1)) == 0.
Check that the set bit is at an even position: (n & 0x55555555) == n.
Return true if all conditions are met.

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0 and (n & 0x55555555) == n

Time & Space Complexity

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

6. Bit Mask - II

Intuition

Powers of four follow a pattern when divided by 3: 4^k mod 3 = 1 for all non-negative k. This is because 4 = 3 + 1, so 4^k = (3+1)^k, which when expanded always leaves remainder 1.

Powers of two that are not powers of four (like 2, 8, 32) give remainder 2 when divided by 3. This gives us a simple way to distinguish between them.

Algorithm

Check that n is positive.
Check that n is a power of two: (n & (n - 1)) == 0.
Check that n % 3 == 1 to confirm it's specifically a power of four.
Return true if all conditions are met.

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0 and (n % 3 == 1)

Time & Space Complexity

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

Common Pitfalls

Confusing Power of Two with Power of Four

All powers of four are powers of two, but not vice versa. Checking only (n & (n - 1)) == 0 accepts values like 2, 8, and 32 which are powers of two but not four. You must add an additional check to verify the set bit is at an even position.

Floating-Point Precision Errors with Logarithms

Using log(n) / log(4) can introduce floating-point errors. For example, log(64) / log(4) might return 2.9999999... instead of exactly 3. Comparing with == 0 after modulo may incorrectly reject valid powers of four. Consider rounding or using integer-based approaches instead.