# Power of Three
**Difficulty:** EASY
[External](https://leetcode.com/problems/power-of-three)
Canonical: https://scaleengineer.com/dsa/problems/power-of-three
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Recursion](https://scaleengineer.com/dsa/patterns/recursion)
**Companies:** [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs)
---
## Problem
Given an integer `n`, return _`true` if it is a power of three. Otherwise, return `false`_.

An integer `n` is a power of three, if there exists an integer `x` such that `n == 3x`.

**Example 1:**

**Input:** n = 27
**Output:** true
**Explanation:** 27 = 33

**Example 2:**

**Input:** n = 0
**Output:** false
**Explanation:** There is no x where 3x = 0.

**Example 3:**

**Input:** n = -1
**Output:** false
**Explanation:** There is no x where 3x = (-1).

**Constraints:**

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

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

# Approaches
## Recursive Division
This approach uses recursion to repeatedly check if the number can be divided by 3. The logic is broken down into base cases: a number is a power of three if, after being divided by 3 some number of times, it becomes 1. If at any point it's not divisible by 3 (and is not 1), it's not a power of three.
**Time:** O(log n)
The number of recursive calls is proportional to the logarithm of `n` to the base 3. In each call, we perform constant time operations. · **Space:** O(log n)
Each recursive call adds a new frame to the call stack. The depth of the recursion is the number of times `n` can be divided by 3, which is `log_3(n)`.
**Pros:** The code can be seen as an elegant and direct translation of the mathematical definition.; It avoids explicit loop constructs.
**Cons:** Less space-efficient than the iterative approach due to the recursion call stack.; Can lead to a `StackOverflowError` for inputs larger than the standard integer types, although this is not an issue with the given constraints.
### Explanation
The function `isPowerOfThree` is defined recursively. It first handles the base cases. Any number less than or equal to 0 cannot be a power of three. The number 1 is the base case for a successful path (`3^0 = 1`). If the current number `n` is not divisible by 3, it breaks the chain of powers of three, so we return `false`. Otherwise, the function calls itself with the argument `n / 3`, continuing the process until a base case is met.

```java
class Solution {
    public boolean isPowerOfThree(int n) {
        if (n <= 0) {
            return false;
        }
        if (n == 1) {
            return true;
        }
        if (n % 3 != 0) {
            return false;
        }
        return isPowerOfThree(n / 3);
    }
}
```
### Algorithm
- If `n <= 0`, it cannot be a power of three, so return `false`.
- If `n == 1`, it is `3^0`, which is a power of three, so return `true`.
- If `n` is not divisible by 3 (`n % 3 != 0`), it cannot be a power of three (unless it's 1, which is already handled), so return `false`.
- If none of the above, the number is a positive multiple of 3. Make a recursive call with `n / 3` and return its result.

## Iterative Division
This is a straightforward and intuitive approach that uses a loop to repeatedly divide the input number `n` by 3. If the number is truly a power of three, this process will eventually result in 1. If the loop finishes and the number is not 1, it was not a power of three.
**Time:** O(log n)
The number of divisions performed in the `while` loop is `log_3(n)`. For each iteration, the operations are constant time. · **Space:** O(1)
This approach uses only a fixed number of variables, so the space required is constant.
**Pros:** Easy to understand and implement.; Very efficient in terms of space complexity.
**Cons:** Uses a loop, which the follow-up question asks to avoid.; Slower than constant-time mathematical or pre-computation approaches.
### Explanation
We start by checking if `n` is a positive number, as powers of three cannot be zero or negative. Then, we enter a `while` loop. The condition for the loop is `n % 3 == 0`, meaning it continues as long as `n` is perfectly divisible by 3. Inside the loop, we perform the division `n = n / 3`. This effectively strips away factors of 3. If the original `n` was `3^x`, after `x` iterations, `n` will become 1. If `n` had other prime factors, the loop would terminate earlier, leaving `n` as a number other than 1. Finally, we return the result of the check `n == 1`.

```java
class Solution {
    public boolean isPowerOfThree(int n) {
        if (n <= 0) {
            return false;
        }
        while (n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
}
```
### Algorithm
- First, handle the edge case: if `n` is not positive (`n <= 0`), return `false` since powers of three are always positive.
- Use a `while` loop that continues as long as `n` is greater than 1 and is divisible by 3.
- Inside the loop, update `n` by dividing it by 3 (`n /= 3`).
- After the loop terminates, check if the final value of `n` is 1. If it is, the original number was a power of three.

## Logarithmic Calculation
This approach leverages a mathematical property. If an integer `n` is a power of three, it can be expressed as `n = 3^x` for some integer `x`. By taking the logarithm of both sides, we get `log(n) = x * log(3)`, which means `x = log(n) / log(3)`. The problem then reduces to checking if this calculated `x` is an integer.
**Time:** O(1)
The `Math.log10` and other arithmetic operations are typically considered constant time for fixed-size numeric types. · **Space:** O(1)
No extra space that scales with the input size is required.
**Pros:** Provides a constant-time solution.; Satisfies the follow-up requirement of not using loops or recursion.
**Cons:** Relies on floating-point arithmetic, which can introduce precision errors. A simple check like `x % 1 == 0` might fail for certain inputs (e.g., `log10(243)/log10(3)` might evaluate to `4.999...`).; Requires careful handling of the floating-point comparison to be robust.
### Explanation
This method provides a solution without loops or recursion, as requested by the follow-up. First, we ensure `n` is positive. Then, we compute the value of the exponent `x` using the change of base formula for logarithms: `x = log_b(n) = log_k(n) / log_k(3)`. Java's `Math.log10` or `Math.log` can be used. The crucial part is to verify if the result is an integer. A naive check `result % 1 == 0` is unreliable due to floating-point representation errors. A more robust method is to check if the absolute difference between the result and its nearest integer (`Math.round(result)`) is smaller than a tiny tolerance value (epsilon, e.g., `1e-10`).

```java
class Solution {
    public boolean isPowerOfThree(int n) {
        if (n <= 0) {
            return false;
        }
        double logResult = Math.log10(n) / Math.log10(3);
        // Check if the result is very close to an integer.
        return Math.abs(logResult - Math.round(logResult)) < 1e-10;
    }
}
```
### Algorithm
- Handle the edge case: if `n <= 0`, return `false` because the logarithm is not defined for non-positive numbers.
- Calculate `x = log(n) / log(3)`. We can use any logarithm base, such as base 10 or the natural logarithm.
- Check if the resulting `x` is an integer. Due to potential floating-point inaccuracies, it's safer to check if `x` is very close to its rounded value rather than using a simple modulo check like `x % 1 == 0`.

## Integer Constraint Magic
This is the most efficient approach and directly answers the follow-up question. It leverages the fact that the input `n` is a 32-bit signed integer. We can pre-calculate the largest power of three that fits within this integer range. Any other power of three must be a divisor of this largest power.
**Time:** O(1)
The solution involves only a few primitive operations (a comparison and a modulo), which take constant time. · **Space:** O(1)
No extra space is used.
**Pros:** Extremely fast with O(1) time complexity.; Avoids loops, recursion, and floating-point precision issues.; Very simple and concise code.
**Cons:** This solution is a 'trick' that is only applicable because of the specific constraint that `n` is a 32-bit integer.; It is not a general solution for arbitrary-precision numbers (e.g., `BigInteger`).
### Explanation
The maximum value for a Java `int` is `2^31 - 1`, which is `2,147,483,647`. We can find the largest power of 3 that does not exceed this value:
- `3^19 = 1,162,261,467`
- `3^20 = 3,486,784,401` (which is too large)
So, the largest power of 3 that can be represented as an `int` is `3^19`.

The number `3^19` has only one prime factor: 3. If a number `n` is a power of three (i.e., `n = 3^x` for some `x`), its only prime factor is also 3. This means that if `n` is a power of three, it must evenly divide `3^19`. Conversely, if a positive number `n` evenly divides `3^19`, its prime factors must be a subset of the prime factors of `3^19`, meaning its only prime factor can be 3. Thus, `n` must be a power of three. This leads to a very simple and fast check.

```java
class Solution {
    public boolean isPowerOfThree(int n) {
        // 1162261467 is 3^19, the largest power of 3 that fits in a 32-bit signed integer.
        return n > 0 && 1162261467 % n == 0;
    }
}
```
### Algorithm
- First, check if `n` is positive. Powers of three are always positive.
- The largest power of 3 that fits within a 32-bit signed integer is `3^19`, which is `1162261467`.
- If `n` is a power of three, it must be a divisor of this largest power of three.
- Therefore, the check simplifies to `n > 0 && 1162261467 % n == 0`.

# Solutions
### Java

```java
class Solution {
public
  boolean isPowerOfThree(int n) { return n > 0 && 1162261467 % n == 0; }
}

```

### JavaScript

```javascript
/** * @param {number} n * @return {boolean} */ var isPowerOfThree = function (
  n,
) {
  return n > 0 && 1162261467 % n == 0;
};

```

### CPP

```cpp
class Solution {
public:
  bool isPowerOfThree(int n) { return n > 0 && 1162261467 % n == 0; }
};

```

### Python

```python
class Solution : def isPowerOfThree ( self , n : int ) -> bool : return n > 0 and 1162261467 % n == 0
```