Code Implementation

class Solution:
    def newInteger(self, n: int) -> int:
        # Convert n to base 9 and interpret as decimal
        res = 0
        base = 1
        while n > 0:
            res += (n % 9) * base
            n //= 9
            base *= 10
        return res
      

class Solution {
public:
    int newInteger(int n) {
        int res = 0, base = 1;
        while (n > 0) {
            res += (n % 9) * base;
            n /= 9;
            base *= 10;
        }
        return res;
    }
};
      

class Solution {
    public int newInteger(int n) {
        int res = 0, base = 1;
        while (n > 0) {
            res += (n % 9) * base;
            n /= 9;
            base *= 10;
        }
        return res;
    }
}
      

var newInteger = function(n) {
    let res = 0, base = 1;
    while (n > 0) {
        res += (n % 9) * base;
        n = Math.floor(n / 9);
        base *= 10;
    }
    return res;
};
      

Problem Description

The "Remove 9" problem asks you to find the nth positive integer that does not contain the digit '9' in its decimal representation. For example, if n = 9, the answer is 10 (since 9 is skipped).

• Given a positive integer n, return the nth integer in the sequence of positive numbers that do not have the digit '9'.
• Each number in the sequence must not contain the digit '9' anywhere.
• There is exactly one valid answer for each n.

Thought Process

At first glance, you might think to simply iterate from 1 upwards, skipping numbers containing '9', until you reach the nth valid number. While this brute-force method works for small n, it's inefficient for large values.

To optimize, it's helpful to notice a pattern: the sequence of numbers without any '9' digits is like counting in base 9. For example, the numbers 1, 2, ..., 8, 10, 11, ... (skipping 9, 19, 29, etc.) correspond to numbers written in base 9, but interpreted as decimal.

Recognizing this allows us to convert n directly to its base-9 representation and interpret that as the answer.

Solution Approach

• Step 1: Understand that the set of numbers without '9' digits is equivalent to counting in base 9.
• Step 2: Convert n to its base-9 representation. For example, if n = 10, the base-9 representation is "11".
• Step 3: Interpret this base-9 number as a decimal integer. For n = 10, base-9 "11" is decimal 11.
• Step 4: Return this integer as the answer. This method skips all numbers with '9' and is efficient even for large n.

We use a loop to convert n to base 9 by repeatedly taking n % 9 for the current digit, then dividing n by 9 to process the next digit. We build the result as a decimal number by multiplying each digit by the appropriate power of 10.

Example Walkthrough

Let's walk through an example with n = 15:

1. Convert 15 to base 9:
   • 15 divided by 9 is 1, remainder 6. So the least significant digit is 6.
   • 1 divided by 9 is 0, remainder 1. So the next digit is 1.
   • Base-9 representation: "16"
2. Interpret "16" as a decimal number: 16.
3. Let's check the sequence of numbers without '9': 1,2,3,4,5,6,7,8,10,11,12,13,14,15,16...
   • The 15th number is 16, which matches our result.

This process works for any value of n, efficiently skipping all numbers with the digit '9'.

Time and Space Complexity

• Brute-force Approach:
  • Time Complexity: O(n * d), where d is the number of digits in each number (to check for '9').
  • This is inefficient for large n because it checks every number up to the answer.
• Optimized Approach (Base-9 Conversion):
  • Time Complexity: O(log₉ n), since we process each base-9 digit of n.
  • Space Complexity: O(1), as we use a few integer variables.
  • This is highly efficient, even for very large n.

Summary

The "Remove 9" problem is elegantly solved by recognizing the pattern between numbers without the digit '9' and base-9 counting. Instead of brute-force filtering, we convert n to base-9 and interpret the result as a decimal number. This provides a fast, simple, and scalable solution that avoids unnecessary computation and leverages number system insights.