# LeetCode 263: Ugly Number

## Problem Restatement

We are given an integer `n`.

Return `True` if `n` is an ugly number.

An ugly number is a positive integer whose prime factors are limited to:

```python
2, 3, 5
```

So a number is ugly if, after removing all factors of `2`, `3`, and `5`, nothing remains except `1`.

The problem constraints are:

```python
-2^31 <= n <= 2^31 - 1
```

`1` is considered ugly because it has no prime factors. Non-positive numbers are not ugly.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer `n` |
| Output | Boolean |
| Ugly number | Positive integer with no prime factors except `2`, `3`, and `5` |
| Special case | `1` is ugly |

Example function shape:

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

## Examples

Example 1:

```python
n = 6
```

Prime factorization:

```python
6 = 2 * 3
```

All prime factors are allowed.

Answer:

```python
True
```

Example 2:

```python
n = 1
```

`1` has no prime factors.

Since it has no forbidden prime factor, it is ugly.

Answer:

```python
True
```

Example 3:

```python
n = 14
```

Prime factorization:

```python
14 = 2 * 7
```

The factor `7` is not allowed.

Answer:

```python
False
```

Example 4:

```python
n = 0
```

Ugly numbers must be positive.

Answer:

```python
False
```

## First Thought: Prime Factorization

A direct way is to factor `n` into primes, then check whether every prime factor is one of:

```python
2, 3, 5
```

This works, but full prime factorization is unnecessary.

We do not care what all factors are.

We only care whether any factor remains after removing all `2`s, `3`s, and `5`s.

## Key Insight

If `n` is ugly, then it can be reduced to `1` by repeatedly dividing by `2`, `3`, and `5`.

For example:

```python
n = 30
```

Divide by `2`:

```python
30 / 2 = 15
```

Divide by `3`:

```python
15 / 3 = 5
```

Divide by `5`:

```python
5 / 5 = 1
```

Since the final value is `1`, `30` is ugly.

For a non-ugly number:

```python
n = 14
```

Divide by `2`:

```python
14 / 2 = 7
```

Now `7` is not divisible by `2`, `3`, or `5`.

The final value is `7`, so `14` is not ugly.

## Algorithm

1. If `n <= 0`, return `False`.
2. For each allowed factor `p` in `[2, 3, 5]`:
   - While `n` is divisible by `p`, divide `n` by `p`.
3. After removing all allowed factors:
   - Return `True` if `n == 1`.
   - Otherwise return `False`.

## Walkthrough

Use:

```python
n = 12
```

Start with allowed factors:

```python
[2, 3, 5]
```

Divide by `2` while possible:

```python
12 / 2 = 6
6 / 2 = 3
```

Now `3` is no longer divisible by `2`.

Divide by `3`:

```python
3 / 3 = 1
```

Now the value is `1`.

Return:

```python
True
```

Use:

```python
n = 42
```

Divide by `2`:

```python
42 / 2 = 21
```

Divide by `3`:

```python
21 / 3 = 7
```

`7` cannot be divided by `2`, `3`, or `5`.

Return:

```python
False
```

## Correctness

If the algorithm returns `True`, then after repeatedly dividing by `2`, `3`, and `5`, the remaining value is `1`. Therefore the original number was made only from factors `2`, `3`, and `5`. So it has no forbidden prime factor and is ugly.

If the algorithm returns `False`, then after removing all possible factors of `2`, `3`, and `5`, the remaining value is greater than `1`. This remaining value must contain some prime factor other than `2`, `3`, or `5`. Therefore the original number has a forbidden prime factor and is not ugly.

The algorithm also rejects all `n <= 0`, which is correct because ugly numbers are positive.

Therefore the algorithm returns the correct result.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(log n)` | Each division reduces `n` by at least a factor of `2` |
| Space | `O(1)` | Only a few variables are used |

## Implementation

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

        for factor in (2, 3, 5):
            while n % factor == 0:
                n //= factor

        return n == 1
```

## Code Explanation

First handle non-positive input:

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

This is necessary because ugly numbers are positive.

Then iterate through the only allowed prime factors:

```python
for factor in (2, 3, 5):
```

For each allowed factor, remove it completely:

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

After all divisions, `n == 1` means nothing forbidden remains.

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

## Testing

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

    assert s.isUgly(6) is True
    assert s.isUgly(1) is True
    assert s.isUgly(14) is False
    assert s.isUgly(0) is False
    assert s.isUgly(-6) is False
    assert s.isUgly(30) is True
    assert s.isUgly(42) is False
    assert s.isUgly(2 ** 10) is True
    assert s.isUgly((2 ** 4) * (3 ** 3) * (5 ** 2)) is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `6` | Uses allowed factors `2` and `3` |
| `1` | No prime factors |
| `14` | Contains forbidden factor `7` |
| `0` | Non-positive input |
| `-6` | Negative input |
| `30` | Uses all allowed factors |
| `42` | Contains forbidden factor after division |
| Power of `2` | Repeated allowed factor |
| Product of `2`, `3`, and `5` | Larger ugly number |