# LeetCode 264: Ugly Number II

## Problem Restatement

We are given an integer `n`.

Return the `n`th ugly number.

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

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

The sequence starts with:

```python
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...
```

`1` is treated as an ugly number.

The constraint is:

```python
1 <= n <= 1690
```

The official examples include `n = 10 -> 12` and `n = 1 -> 1`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | The `n`th ugly number |
| Ugly factor rule | Prime factors may only be `2`, `3`, and `5` |
| First ugly number | `1` |

Example function shape:

```python
def nthUglyNumber(n: int) -> int:
    ...
```

## Examples

Example 1:

```python
n = 10
```

The first ten ugly numbers are:

```python
1, 2, 3, 4, 5, 6, 8, 9, 10, 12
```

The 10th ugly number is:

```python
12
```

Answer:

```python
12
```

Example 2:

```python
n = 1
```

The first ugly number is:

```python
1
```

Answer:

```python
1
```

## First Thought: Check Every Integer

A direct approach is to test every positive integer.

For each number, use the method from LeetCode 263:

1. Divide out all factors of `2`.
2. Divide out all factors of `3`.
3. Divide out all factors of `5`.
4. If the result is `1`, the number is ugly.

Keep counting ugly numbers until the `n`th one appears.

This works, but it wastes time checking many numbers that are not ugly.

## Problem With Brute Force

The ugly numbers become more spread out as values grow.

Checking every integer means we spend work on numbers like:

```python
7, 11, 13, 14, 17, 19, 21, ...
```

Most of these contain forbidden prime factors.

Instead of checking all numbers, we should generate ugly numbers directly.

## Key Insight

Every ugly number after `1` comes from a smaller ugly number multiplied by one of:

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

So if we already know the ugly sequence, the next ugly number must be the smallest value among:

```python
some_previous_ugly * 2
some_previous_ugly * 3
some_previous_ugly * 5
```

We maintain three pointers:

| Pointer | Meaning |
|---|---|
| `i2` | The smallest ugly number index whose `* 2` candidate has not been used |
| `i3` | The smallest ugly number index whose `* 3` candidate has not been used |
| `i5` | The smallest ugly number index whose `* 5` candidate has not been used |

At each step, the next ugly number is:

```python
min(ugly[i2] * 2, ugly[i3] * 3, ugly[i5] * 5)
```

After choosing the next number, advance every pointer that produced it.

Advancing every matching pointer is important because duplicates can be generated in multiple ways.

For example:

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

We should include `6` only once.

## Algorithm

1. Create an array `ugly` of length `n`.
2. Set:
   ```python id="syrqbx"
   ugly[0] = 1
   ```
3. Start three pointers:
   ```python id="r40vou"
   i2 = i3 = i5 = 0
   ```
4. For each next position from `1` to `n - 1`:
   - Compute:
     ```python id="nq12vi"
     next2 = ugly[i2] * 2
     next3 = ugly[i3] * 3
     next5 = ugly[i5] * 5
     ```
   - Let:
     ```python id="i78bzh"
     nxt = min(next2, next3, next5)
     ```
   - Store `nxt` in the sequence.
   - If `nxt == next2`, increment `i2`.
   - If `nxt == next3`, increment `i3`.
   - If `nxt == next5`, increment `i5`.
5. Return:
   ```python id="naddig"
   ugly[n - 1]
   ```

## Walkthrough

Use:

```python
n = 10
```

Start:

```python
ugly = [1]
i2 = 0
i3 = 0
i5 = 0
```

Candidates:

| Step | `ugly[i2] * 2` | `ugly[i3] * 3` | `ugly[i5] * 5` | Next |
|---|---:|---:|---:|---:|
| 1 | 2 | 3 | 5 | 2 |
| 2 | 4 | 3 | 5 | 3 |
| 3 | 4 | 6 | 5 | 4 |
| 4 | 6 | 6 | 5 | 5 |
| 5 | 6 | 6 | 10 | 6 |
| 6 | 8 | 9 | 10 | 8 |
| 7 | 10 | 9 | 10 | 9 |
| 8 | 10 | 12 | 10 | 10 |
| 9 | 12 | 12 | 15 | 12 |

So the first ten ugly numbers are:

```python
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]
```

Return:

```python
12
```

## Correctness

The array `ugly` is built in increasing order.

Initially, `ugly[0] = 1`, which is the first ugly number.

Every later ugly number must be formed by multiplying a smaller ugly number by `2`, `3`, or `5`. Therefore, the next possible ugly number must be one of the three candidate streams:

```python
ugly[i2] * 2
ugly[i3] * 3
ugly[i5] * 5
```

The pointers always refer to the first candidate in each stream that has not already been passed.

Taking the minimum of these three candidates gives the smallest ugly number not yet added.

When the chosen value equals one or more candidate streams, all matching pointers are advanced. This removes duplicates such as `6`, `10`, `15`, and `30`, which can be produced by more than one factor path.

Thus each step appends exactly the next ugly number, in order, without duplicates.

After filling `n` values, `ugly[n - 1]` is the `n`th ugly number.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We generate one ugly number per iteration |
| Space | `O(n)` | We store the first `n` ugly numbers |

## Implementation

```python
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        ugly = [1] * n

        i2 = 0
        i3 = 0
        i5 = 0

        for i in range(1, n):
            next2 = ugly[i2] * 2
            next3 = ugly[i3] * 3
            next5 = ugly[i5] * 5

            nxt = min(next2, next3, next5)
            ugly[i] = nxt

            if nxt == next2:
                i2 += 1
            if nxt == next3:
                i3 += 1
            if nxt == next5:
                i5 += 1

        return ugly[n - 1]
```

## Code Explanation

The array starts with `1`:

```python
ugly = [1] * n
```

The first value is already correct, so we fill from index `1`.

The three pointers start at the first ugly number:

```python
i2 = 0
i3 = 0
i5 = 0
```

At every step, compute the next possible value from each multiplication stream:

```python
next2 = ugly[i2] * 2
next3 = ugly[i3] * 3
next5 = ugly[i5] * 5
```

The smallest candidate becomes the next ugly number:

```python
nxt = min(next2, next3, next5)
ugly[i] = nxt
```

Then advance every pointer that produced `nxt`:

```python
if nxt == next2:
    i2 += 1
if nxt == next3:
    i3 += 1
if nxt == next5:
    i5 += 1
```

Using three separate `if` statements removes duplicates.

Finally:

```python
return ugly[n - 1]
```

returns the `n`th ugly number.

## Testing

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

    assert s.nthUglyNumber(1) == 1
    assert s.nthUglyNumber(2) == 2
    assert s.nthUglyNumber(3) == 3
    assert s.nthUglyNumber(10) == 12
    assert s.nthUglyNumber(11) == 15
    assert s.nthUglyNumber(15) == 24
    assert s.nthUglyNumber(1690) == 2123366400

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `1` | First ugly number |
| `2`, `3` | Early sequence order |
| `10` | Official example |
| `11` | Checks next value after official prefix |
| `15` | Confirms duplicate handling across streams |
| `1690` | Upper constraint boundary |