# LeetCode 660: Remove 9

## Problem Restatement

We imagine the positive integers after removing every number that contains the digit `9`.

The remaining sequence begins like this:

```text
1, 2, 3, 4, 5, 6, 7, 8,
10, 11, 12, ...
```

Notice that:

```text
9
19
29
90
...
```

are all removed because they contain digit `9`.

We are given an integer `n`.

Return the `n`th positive integer in the filtered sequence.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | The `n`th positive integer that does not contain digit `9` |
| Removed numbers | Any number containing digit `9` |

Example function shape:

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

## Examples

Consider:

```python
n = 1
```

The filtered sequence starts with:

```text
1, 2, 3, ...
```

So the answer is:

```python
1
```

Now consider:

```python
n = 8
```

The first eight valid numbers are:

```text
1, 2, 3, 4, 5, 6, 7, 8
```

So the answer is:

```python
8
```

Now consider:

```python
n = 9
```

The next valid number after `8` is:

```text
10
```

because `9` is removed.

So the answer is:

```python
10
```

Another example:

```python
n = 10
```

The sequence becomes:

```text
1, 2, 3, 4, 5, 6, 7, 8, 10, 11
```

So the answer is:

```python
11
```

## First Thought: Check Every Number

A direct approach is:

1. Start from `1`.
2. Check whether the number contains digit `9`.
3. Count only valid numbers.
4. Stop when we reach the `n`th valid number.

For example:

```text
1 ✓
2 ✓
...
8 ✓
9 ✗
10 ✓
```

This works, but it becomes slow for large `n`.

We need a mathematical pattern.

## Key Insight

The allowed digits are:

```text
0, 1, 2, 3, 4, 5, 6, 7, 8
```

There are exactly:

```text
9 digits
```

This suggests:

```text
base 9
```

In base `9`, digits range from `0` to `8`.

That perfectly matches the allowed decimal digits after removing `9`.

The important observation is:

```text
The nth valid number is simply the base-9 representation of n, interpreted as a decimal number.
```

## Understanding the Mapping

Look at the first few base-9 numbers:

| Decimal `n` | Base-9 form |
|---|---|
| `1` | `1` |
| `2` | `2` |
| `3` | `3` |
| `4` | `4` |
| `5` | `5` |
| `6` | `6` |
| `7` | `7` |
| `8` | `8` |
| `9` | `10` |
| `10` | `11` |
| `11` | `12` |

Now compare with the filtered sequence:

```text
1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, ...
```

They are identical.

Why?

Because base-9 numbers never use digit `9`.

So every base-9 representation already satisfies the rule automatically.

## Algorithm

Convert `n` into base `9`.

Then interpret the resulting digits as a normal decimal integer.

For example:

```python
n = 9
```

Base-9 representation:

```text
10
```

Return:

```python
10
```

Another example:

```python
n = 15
```

Base-9 representation:

```text
16
```

So the answer is:

```python
16
```

## Base-9 Conversion

Repeatedly:

1. Take:

```python
n % 9
```

to get the last base-9 digit.

2. Divide:

```python
n //= 9
```

3. Continue until `n == 0`.

The digits are produced from right to left.

## Correctness

The valid sequence contains exactly the positive integers whose decimal representations use only digits from `0` to `8`.

Base-9 numbers also use exactly the digits from `0` to `8`.

When positive integers are written in increasing order in base `9`, they enumerate all finite digit strings over `{0,1,2,3,4,5,6,7,8}` in increasing numeric order.

Therefore, if we take the base-9 representation of `n` and interpret its digits as a decimal number, we obtain exactly the `n`th positive integer that does not contain digit `9`.

The conversion algorithm computes the base-9 representation correctly using repeated division and remainder operations.

So the returned number is exactly the required answer.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(log₉ n)` | Each step divides `n` by `9` |
| Space | `O(log₉ n)` | Digits are stored during conversion |

## Implementation

```python