Remove 9

Problem Statement

The problem entails generating a specific integer sequence starting from 1 and then removing any integer within that sequence which contains the digit '9'. For example, integers like 9, 19, 29, and so forth will be excluded. What is left forms a new sequence: [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, ...] and so on.

Given an integer n, the task is to return the nth integer in this new sequence where this sequence does not contain the digit '9' at any position, and n is 1-indexed. This means for n = 1, the output should be the first integer in the transformed list and for n = 2 the second, and so on. The main challenge lies in calculating the nth term efficiently without generating excessively large sequences explicitly, especially given the constraints.

Examples

Example 1

Input:

n = 9

Output:

10

Example 2

Input:

n = 10

Output:

11

Constraints

• 1 <= n <= 8 * 108

Approach and Intuition

To tackle this problem, we first need a deeper understanding of how numbers containing the digit '9' are to be filtered out to form the new sequence. The task then reduces to finding which number corresponds to the nth position in this filtered list.

Here's an intuitive step-by-step approach to deriving a solution:

1. Understanding the Numbers: Recognize that what we're effectively dealing with is a base-9-like system, where each digit can be from 1-8 (since 9 is excluded).

2. Mapping to Base-9: Convert the given index n to a base-9 number. This is because, at every decimal digit place, only digits 1-8 are valid due to the exclusion of 9.

3. Direct Computation or Construction: Construct the number by translating each computed base-9 digit back into a base-10 number but without the digit '9'.

   • For example, if n = 9, the output is 10 which is the next number in our sequence avoiding any number containing '9'.

   • Proceed to derive numbers and check if any digit contains '9'. If a '9' is found, skip that number and continue to the next number.

4. Optimization Awareness: Combining the conversion and direct checking may still involve considerable computation given the upper constraint of n being up to 800 million. Efficient conversion and checking mechanisms need to be implemented to cope with large input sizes without generating the entire sequence up to that point.

The process essentially involves mapping each sequence position n to its number in a base-9-like environment affected by exclusion of the number '9'. Implementation can then iterate and calculate directly from this understanding, potentially optimizing via mathematical interpretations and avoiding direct brute force up to high ns.

Solutions

class Solution {
    public int convertToBase9(int number) {
        return Integer.parseInt(Integer.toString(number, 9));
    }
}

class Solution:
    def baseNineConverter(self, number):
        result = ''
        while number:
            result = str(number % 9) + result
            number //= 9
    
        return int(result)