# Power of Four
**Difficulty:** EASY
[External](https://leetcode.com/problems/power-of-four)
Canonical: https://scaleengineer.com/dsa/problems/power-of-four
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Recursion](https://scaleengineer.com/dsa/patterns/recursion), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Companies:** [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Wix](https://scaleengineer.com/companies/wix), [Two Sigma](https://scaleengineer.com/companies/two-sigma)
---
## Problem
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 == 4x`.

**Example 1:**

**Input:** n = 16
**Output:** true

**Example 2:**

**Input:** n = 5
**Output:** false

**Example 3:**

**Input:** n = 1
**Output:** true

**Constraints:**

* `-231 <= n <= 231 - 1`

**Follow up:** Could you solve it without loops/recursion?

# Approaches
## Iterative Approach
This approach uses a loop to check if the given number `n` is a power of four. We start with a variable, say `powerOfFour`, initialized to 1. We repeatedly multiply this variable by 4 in a loop. If `powerOfFour` becomes equal to `n` at any point, we've found that `n` is a power of four. If `powerOfFour` exceeds `n`, it means `n` cannot be a power of four, as we've passed the potential value.
**Time:** O(log₄ n). The number of iterations in the loop is proportional to the exponent `x` where `4^x` is close to `n`. This is logarithmic with base 4. · **Space:** O(1). We only use a few variables to store the state, regardless of the input size.
**Pros:** Simple to understand and implement.; Works correctly for all valid integer inputs.
**Cons:** Less efficient than constant-time solutions.; Does not satisfy the follow-up constraint of solving the problem without loops or recursion.
### Explanation
The core idea is to generate powers of four one by one and compare them with the input number `n`. We start with `4^0 = 1`. In each step of a loop, we multiply our current number by 4 to get the next power of four. We stop when our generated number is greater than or equal to the input `n`. Finally, we check if our number is exactly equal to `n`.

```java
class Solution {
    public boolean isPowerOfFour(int n) {
        if (n <= 0) {
            return false;
        }
        long powerOfFour = 1;
        while (powerOfFour < n) {
            powerOfFour *= 4;
        }
        return powerOfFour == n;
    }
}
```
### Algorithm
1. Handle the edge case: If `n` is less than or equal to 0, it cannot be a power of four, so return `false`.
2. Initialize a long variable `powerOfFour` to 1. We use `long` to prevent overflow when `powerOfFour * 4` exceeds `Integer.MAX_VALUE`.
3. Start a `while` loop that continues as long as `powerOfFour` is less than `n`.
4. Inside the loop, update `powerOfFour` by multiplying it by 4 (`powerOfFour *= 4`).
5. After the loop, check if `powerOfFour` is equal to `n`. If they are equal, `n` is a power of four. Otherwise, it is not.

## Mathematical Approach using Logarithms
This approach leverages the mathematical properties of logarithms. If an integer `n` is a power of four, it can be expressed as `n = 4^x` for some integer `x`. By taking the logarithm base 4 of both sides, we get `log₄(n) = x`. This means that for `n` to be a power of four, `log₄(n)` must be an integer. We can use the change of base formula `log_b(a) = log_c(a) / log_c(b)` to calculate this value and check if it's an integer.
**Time:** O(1). The `Math.log()` function is typically implemented in a way that its complexity is considered constant for the purpose of algorithmic analysis. · **Space:** O(1). No extra space proportional to the input size is used.
**Pros:** Solves the problem in constant time.; Satisfies the follow-up requirement of not using loops or recursion.; The code is very concise.
**Cons:** Relies on floating-point arithmetic, which can introduce precision errors for very large numbers, although it's generally safe for standard integer types.
### Explanation
This method directly solves for the exponent `x` in the equation `n = 4^x`. Since most programming languages provide a natural logarithm (`ln` or `log`) or base-10 logarithm (`log10`), we can compute `log₄(n)` as `log(n) / log(4)`. The result of this division will be a floating-point number. If this number is a whole number (i.e., has no fractional part), then `n` is a perfect power of four.

```java
class Solution {
    public boolean isPowerOfFour(int n) {
        if (n <= 0) {
            return false;
        }
        double logValue = Math.log(n) / Math.log(4);
        // Check if the result is an integer. 
        // Comparing with its floor or ceiling also works.
        return logValue == (int)logValue;
    }
}
```
### Algorithm
1. Handle the edge case: If `n` is less than or equal to 0, return `false` as logarithms are not defined for non-positive numbers.
2. Calculate `x = log(n) / log(4)`. This uses the change of base formula for logarithms.
3. Check if the result `x` is an integer. A simple way to do this is to check if `x` has no fractional part, for example, by comparing it to its truncated integer value: `x == (int)x`.
4. If `x` is an integer, `n` is a power of four; otherwise, it is not.

## Bit Manipulation with Modulo Arithmetic
This is a clever constant-time solution that avoids floating-point math and "magic number" bitmasks. It relies on a combination of bit manipulation and a mathematical property of powers of four. A number `n` is a power of four if and only if it meets two criteria: it must be a power of two, and among powers of two, it must satisfy a specific condition that can be checked with modulo arithmetic.
**Time:** O(1). The solution involves a few bitwise and arithmetic operations, which are all constant time. · **Space:** O(1). No extra space is used.
**Pros:** Extremely efficient O(1) time complexity.; Uses only robust integer arithmetic.; Satisfies the follow-up by avoiding loops/recursion.; Arguably more elegant than using a hardcoded bitmask.
**Cons:** The mathematical reasoning behind the `n % 3 == 1` check might not be immediately obvious to everyone.
### Explanation
First, we establish that `n` must be a power of two. This is because `4^x = (2^2)^x = 2^(2x)`, so any power of four is also a power of two. The check `(n & (n - 1)) == 0` (for `n > 0`) confirms this.

Next, we need to differentiate powers of four (e.g., 1, 4, 16, 64) from other powers of two (e.g., 2, 8, 32). Let's look at their values modulo 3:
- Powers of 4: `4^x = (3+1)^x ≡ 1^x ≡ 1 (mod 3)`.
- Other powers of 2: `2 * 4^x ≡ 2 * 1 ≡ 2 (mod 3)`.

So, a power of two is a power of four if and only if `n % 3 == 1`.

```java
class Solution {
    public boolean isPowerOfFour(int n) {
        // 1. n > 0: Must be positive.
        // 2. (n & (n - 1)) == 0: Must be a power of 2.
        // 3. n % 3 == 1: Differentiates powers of 4 from other powers of 2.
        return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1;
    }
}
```
### Algorithm
1. **Check for positive number:** `n > 0`. Powers of four are always positive.
2. **Check for power of two:** `(n & (n - 1)) == 0`. This bitwise trick efficiently verifies if a number has only one bit set to '1' in its binary representation, which is a necessary condition for being a power of two (and thus for being a power of four).
3. **Check the modulo condition:** `n % 3 == 1`. This condition distinguishes powers of four from other powers of two. Any power of four (`4^x`) modulo 3 is 1, while other powers of two (`2 * 4^x`) modulo 3 are 2.
4. Combine all three checks. If all are true, `n` is a power of four.

## Bit Manipulation with Bitmask
This is a highly efficient approach that solves the problem without loops or recursion by directly analyzing the binary representation of the number. A number `n` is a power of four if and only if it satisfies three conditions:
1. `n` must be positive.
2. `n` must be a power of two (i.e., have only one '1' bit in its binary form).
3. The single '1' bit must be at an even-numbered position (0, 2, 4, ... counting from the right).
**Time:** O(1). All operations are single, fast CPU instructions. · **Space:** O(1). No extra space is used.
**Pros:** Extremely fast and efficient with O(1) time complexity.; A classic and widely recognized bit manipulation technique.; Satisfies the follow-up constraint of not using loops or recursion.
**Cons:** The bitmask `0x55555555` can seem like a "magic number" if the underlying logic is not understood.
### Explanation
The first two conditions (`n > 0` and `(n & (n - 1)) == 0`) establish that `n` is a power of two. The third condition is the key to filtering for powers of four. Powers of four have their single set bit at positions corresponding to even powers of two (`2^0`, `2^2`, `2^4`, etc.).

The bitmask `0x55555555` is a 32-bit integer where the bits at even positions (0, 2, ..., 30) are set to 1, and bits at odd positions are 0. Its binary representation is `01010101010101010101010101010101`.

When we perform `n & 0x55555555`, if the single set bit in `n` is at an even position, it will be preserved, and the result will be `n`. If the set bit is at an odd position (meaning `n` is a power of two but not a power of four), it will be masked out, and the result will be 0.

```java
class Solution {
    public boolean isPowerOfFour(int n) {
        // 1. n > 0: Must be positive.
        // 2. (n & (n - 1)) == 0: Must be a power of 2 (only one bit set).
        // 3. (n & 0x55555555) == n: The set bit must be at an even position.
        return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) == n;
    }
}
```
### Algorithm
1. **Check for positive number:** `n > 0`. Powers of four are positive (1, 4, 16, ...).
2. **Check for power of two:** `(n & (n - 1)) == 0`. This ensures the number's binary representation has exactly one bit set to '1'.
3. **Check for '1' bit position:** The set bit for a power of four (`4^x = 2^(2x)`) is always at an even-numbered position (0, 2, 4, ...). We can use a bitmask `0x55555555` (binary `0101...0101`), which has '1's only at the even positions. If `n` is a power of four, ANDing it with this mask will result in `n` itself, as its single '1' bit will align with a '1' in the mask.
4. Combine all three checks: `return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) == n;`

# Solutions
### Java

```java
class Solution {
public
  boolean isPowerOfFour(int n) {
    return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
  }
}

```

### JavaScript

```javascript
/** * @param {number} n * @return {boolean} */ var isPowerOfFour = function (
  n,
) {
  return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
};

```

### Python

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

```

### CPP

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

```