# LeetCode 326: Power of Three

## Problem Restatement

We are given an integer `n`.

Return `true` if `n` is a power of three. Otherwise, return `false`.

A number is a power of three when it can be written as:

```text
n = 3^x
```

where `x` is an integer.

Examples:

```text
27 = 3^3
9  = 3^2
3  = 3^1
1  = 3^0
```

So `27`, `9`, `3`, and `1` are powers of three.

Numbers like `0`, `2`, `6`, `12`, and `45` are not powers of three.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer `n` |
| Output | `true` if `n` is a power of three, otherwise `false` |
| Important condition | `n` may be zero or negative |

Function shape:

```python
def isPowerOfThree(n: int) -> bool:
    ...
```

## Examples

Example 1:

```text
Input: n = 27
Output: true
```

Explanation:

```text
27 = 3 * 3 * 3 = 3^3
```

So `27` is a power of three.

Example 2:

```text
Input: n = 0
Output: false
```

No integer power of three gives `0`.

Example 3:

```text
Input: n = -1
Output: false
```

Powers of three are positive, so `-1` cannot be a power of three.

## First Thought: Brute Force

One direct way is to keep generating powers of three:

```text
1, 3, 9, 27, 81, ...
```

Stop when the generated value becomes greater than or equal to `n`.

If we reach `n`, return `true`.

Otherwise, return `false`.

```python
class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False

        power = 1

        while power < n:
            power *= 3

        return power == n
```

This works, but there is another equally simple way that follows the definition more directly.

## Key Insight

If `n` is a power of three, then it can be divided by `3` repeatedly until it becomes `1`.

For example:

```text
27 -> 9 -> 3 -> 1
```

Every step divides cleanly by `3`.

But consider `45`:

```text
45 -> 15 -> 5
```

Now `5` cannot be divided by `3` cleanly.

So `45` is not a power of three.

The key rule is:

```text
A positive number is a power of three if repeated division by 3 eventually reaches 1 with no remainder.
```

## Algorithm

First handle non-positive numbers.

If `n <= 0`, return `false`.

Then repeatedly divide `n` by `3` while it is divisible by `3`.

At the end, check whether the result is exactly `1`.

Steps:

1. If `n <= 0`, return `false`.
2. While `n % 3 == 0`, divide `n` by `3`.
3. Return whether `n == 1`.

## Walkthrough

Take:

```text
n = 27
```

Since `27` is divisible by `3`, divide:

```text
27 / 3 = 9
```

Since `9` is divisible by `3`, divide:

```text
9 / 3 = 3
```

Since `3` is divisible by `3`, divide:

```text
3 / 3 = 1
```

Now `n` is `1`.

So the answer is `true`.

Now take:

```text
n = 45
```

Divide by `3`:

```text
45 / 3 = 15
```

Divide by `3` again:

```text
15 / 3 = 5
```

Now `5 % 3 != 0`.

We stop. The final value is `5`, not `1`.

So the answer is `false`.

## Correctness

The algorithm only divides by `3` when the current value is exactly divisible by `3`.

If the original number is `3^x`, then each division removes one factor of `3`:

```text
3^x -> 3^(x - 1) -> 3^(x - 2) -> ... -> 3^0
```

Since `3^0 = 1`, every valid power of three eventually becomes `1`.

For a number that has any prime factor other than `3`, repeated division by `3` cannot remove that factor. The process will stop at a value greater than `1`.

For zero or negative numbers, the answer is immediately `false`, since powers of three are positive.

Therefore, the algorithm returns `true` exactly when `n` is a power of three.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(log n)` | Each loop divides `n` by `3` |
| Space | `O(1)` | Only a few variables are used |

More precisely, the number of loop iterations is proportional to `log_3(n)`.

## Implementation

```python
class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False

        while n % 3 == 0:
            n //= 3

        return n == 1
```

## Code Explanation

We first reject zero and negative numbers:

```python
if n <= 0:
    return False
```

Then we divide by `3` as long as division is exact:

```python
while n % 3 == 0:
    n //= 3
```

For a true power of three, this loop eventually reaches `1`.

Finally:

```python
return n == 1
```

This returns `true` for values like `1`, `3`, `9`, and `27`.

It returns `false` for values like `0`, `-1`, `2`, `6`, `12`, and `45`.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.isPowerOfThree(27) == True
    assert s.isPowerOfThree(9) == True
    assert s.isPowerOfThree(3) == True
    assert s.isPowerOfThree(1) == True

    assert s.isPowerOfThree(0) == False
    assert s.isPowerOfThree(-1) == False
    assert s.isPowerOfThree(2) == False
    assert s.isPowerOfThree(6) == False
    assert s.isPowerOfThree(12) == False
    assert s.isPowerOfThree(45) == False

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `27` | Standard positive power of three |
| `9` | Smaller positive power |
| `3` | Base itself |
| `1` | Handles `3^0` |
| `0` | Zero cannot be a power of three |
| `-1` | Negative numbers cannot be powers of three |
| `6` | Divisible by `3` once, but not a pure power |
| `45` | Divisible by `3` several times, then fails |