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:

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

Notice that:

9
19
29
90
...

are all removed because they contain digit 9.

We are given an integer n.

Return the nth positive integer in the filtered sequence.

Input and Output

Example function shape:

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

Examples

Consider:

n = 1

The filtered sequence starts with:

1, 2, 3, ...

So the answer is:

1

Now consider:

n = 8

The first eight valid numbers are:

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

So the answer is:

8

Now consider:

n = 9

The next valid number after 8 is:

10

because 9 is removed.

So the answer is:

10

Another example:

n = 10

The sequence becomes:

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

So the answer is:

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 nth valid number.

For example:

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:

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

There are exactly:

9 digits

This suggests:

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:

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:

Now compare with the filtered sequence:

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:

n = 9

Base-9 representation:

10

Return:

10

Another example:

n = 15

Base-9 representation:

16

So the answer is:

16

Base-9 Conversion

Repeatedly:

1. Take:

n % 9

to get the last base-9 digit.

2. Divide:

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 nth 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

Implementation