LeetCode 660 - Remove 9

LeetCode Problem 660

Difficulty: 🔴 Hard
Topics: Math

Solution

Problem Understanding

The problem defines a modified sequence of positive integers where every number containing the digit 9 is removed. Starting from the natural numbers:

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

we remove all numbers that contain the digit 9:

9, 19, 29, 39, 49, ...

The resulting sequence becomes:

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

The task is to return the nth number in this filtered sequence, using 1-indexing.

The input consists of a single integer n, representing the position in the filtered sequence. The output should be the actual integer that appears at that position after removing all numbers containing 9.

The constraint is important:

1 <= n <= 8 * 10^8

This immediately tells us that brute force enumeration is dangerous. A naive solution that checks every integer one by one would potentially examine hundreds of millions or even billions of numbers before reaching the answer.

An important observation is that numbers are removed specifically because they contain digit 9. This hints that the problem is fundamentally about number representation and digit systems.

Some edge cases worth considering upfront:

• Very small values like n = 1
• Values near transitions such as 8 -> 10
• Large values close to 8 * 10^8
• Numbers whose representation in another base introduces leading zeros or multiple digits
• Ensuring the result itself never contains digit 9

Approaches

Brute Force Approach

The most direct solution is to generate integers starting from 1, skip every number containing digit 9, and count how many valid numbers we have seen.

For example:

1 -> valid
2 -> valid
...
8 -> valid
9 -> invalid
10 -> valid

We continue until we find the nth valid number.

To determine whether a number is valid, we can repeatedly extract digits and check whether any digit equals 9.

This approach is correct because it explicitly constructs the sequence exactly as defined in the problem statement. However, it is far too slow for the given constraints. If n is extremely large, we may need to inspect close to a billion numbers.

Key Insight

The crucial observation is that the filtered sequence behaves exactly like base-9 numbering.

In base-9, digits range from:

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

Notice that digit 9 never appears.

If we write integers in base-9 and interpret those digits as ordinary decimal digits, we get precisely the desired sequence.

For example:

Decimal n	Base-9 Representation	Result
1	1	1
2	2	2
8	8	8
9	10	10
10	11	11
17	18	18
18	20	20

This works because base-9 naturally excludes digit 9.

Therefore, the problem reduces to:

Convert n into base-9, then interpret the digits as a decimal integer.

This eliminates brute force entirely.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k log k)	O(1)	Checks every number individually until the nth valid number is found
Optimal	O(log₉ n)	O(log₉ n)	Convert n directly into base-9

Algorithm Walkthrough

Optimal Algorithm

1. Initialize an empty result representation.

We will repeatedly extract base-9 digits from n. 2. While n > 0, compute the current base-9 digit.

The least significant digit in base-9 is:

digit = n % 9

3. Append this digit to the result.

Since the digit is guaranteed to be between 0 and 8, it never contains 9. 4. Remove the processed digit from n.

n //= 9

5. Continue until all digits are processed.
6. Reverse the collected digits.

Digits are extracted from least significant to most significant, so we reverse them at the end. 7. Convert the digit sequence into an integer and return it.

Why it works

Every positive integer has a unique representation in base-9. Base-9 uses only digits 0 through 8, meaning digit 9 can never appear.

The filtered sequence is exactly the sequence of base-9 numbers interpreted as decimal strings. Therefore, converting n into base-9 directly produces the nth valid number in the sequence.

Python Solution

class Solution:
    def newInteger(self, n: int) -> int:
        digits = []

        while n > 0:
            digits.append(str(n % 9))
            n //= 9

        digits.reverse()

        return int("".join(digits))

The implementation directly follows the mathematical observation.

The while loop converts the input integer into base-9. Each iteration extracts one base-9 digit using modulo % 9.

We store digits as strings because the final answer must be assembled as a decimal-looking number. For example, base-9 digits 1 and 0 should become "10".

Since digits are extracted from right to left, we reverse the list before joining.

Finally, we join all digits into a string and convert it back to an integer.

For example:

n = 9

9 % 9 = 0
9 // 9 = 1

1 % 9 = 1
1 // 9 = 0

Digits collected: ["0", "1"]
Reverse: ["1", "0"]

Result = 10

Go Solution

func newInteger(n int) int {
    result := 0
    place := 1

    for n > 0 {
        digit := n % 9

        result += digit * place

        n /= 9
        place *= 10
    }

    return result
}

The Go implementation avoids string manipulation entirely.

Instead, it constructs the answer numerically. Since every base-9 digit is already a valid decimal digit, we can place digits directly into the result using powers of 10.

The variable place tracks the current decimal position:

1, 10, 100, 1000, ...

This produces the same result more efficiently and avoids reversing arrays or building strings.

Integer overflow is not an issue under the given constraints because the output comfortably fits within Go's standard integer range on LeetCode.

Worked Examples

Example 1

Input: n = 9

We convert 9 to base-9.

Step	n	n % 9	Digit Added	Result Digits
1	9	0	0	["0"]
2	1	1	1	["0", "1"]

Reverse the digits:

["1", "0"]

Final result:

10

Example 2

Input: n = 10

Convert 10 to base-9.

Step	n	n % 9	Digit Added	Result Digits
1	10	1	1	["1"]
2	1	1	1	["1", "1"]

Reverse:

["1", "1"]

Final result:

11

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log₉ n)	Each iteration removes one base-9 digit
Space	O(log₉ n)	The Python solution stores the base-9 digits

The number of iterations equals the number of digits in the base-9 representation of n.

Since:

number of digits = O(log₉ n)

the algorithm is extremely efficient, even for the largest allowed input.

The Go implementation technically uses O(1) auxiliary space because it builds the answer numerically without storing digits separately.

Test Cases

solution = Solution()

assert solution.newInteger(1) == 1        # smallest valid input
assert solution.newInteger(2) == 2        # simple small case
assert solution.newInteger(8) == 8        # last single digit before transition
assert solution.newInteger(9) == 10       # first skipped 9
assert solution.newInteger(10) == 11      # continues after transition
assert solution.newInteger(17) == 18      # largest number without 9 before next jump
assert solution.newInteger(18) == 20      # transition from 18 to 20
assert solution.newInteger(80) == 88      # largest two-digit number without 9
assert solution.newInteger(81) == 100     # base-9 rollover
assert solution.newInteger(100) == 121    # larger conversion test
assert solution.newInteger(500) == 615    # mid-sized value
assert solution.newInteger(1000) == 1331  # multiple base-9 digits

Test Summary

Test	Why
n = 1	Verifies smallest valid input
n = 8	Verifies final single-digit valid number
n = 9	Tests first skipped number transition
n = 10	Ensures numbering continues correctly
n = 17	Tests upper boundary before rollover
n = 18	Verifies multi-digit transition
n = 81	Tests power-of-9 rollover
n = 1000	Confirms correctness on larger values

Edge Cases

Edge Case 1: Smallest Input

When n = 1, the answer should simply be 1.

This is important because some implementations incorrectly assume multiple digits or mishandle initialization logic. Our algorithm handles this naturally because converting 1 to base-9 produces "1".

Edge Case 2: Power of 9 Transitions

Values such as:

9, 81, 729

are important because they create digit rollovers in base-9:

9   -> 10
81  -> 100
729 -> 1000

These transitions are common sources of off-by-one errors. Since the algorithm uses standard base conversion, the rollover behavior is automatically correct.

Edge Case 3: Large Inputs

The constraint allows values up to:

8 * 10^8

A brute force solution would be far too slow here.

The optimal solution remains efficient because it only processes the number of base-9 digits, which is very small compared to the magnitude of the input. Even for the maximum input size, the loop executes only around 10 iterations.

Edge Case 4: Avoiding Digit 9 Completely

A buggy implementation might accidentally generate decimal numbers containing 9.

Our method guarantees correctness mathematically because base-9 digits are restricted to:

0 through 8

Therefore, digit 9 can never appear in the final result.