Vultr DocsLatest Content

Remove 9

Updated on 07 July, 2025
Remove 9 header image

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

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

The given Java solution addresses the problem of converting a decimal integer to its base-9 equivalent. Here's a concise breakdown of how the function operates:

  • The convertToBase9 method receives number as its parameter, this number is a decimal integer that needs to be converted to base-9.
  • The method leverages Java's Integer.toString function to convert the incoming decimal integer to a base-9 string.
  • Subsequently, Integer.parseInt converts the base-9 string back to an integer for the return.

This approach efficiently transforms decimal integers into base-9 integers using built-in Java methods, ensuring precision and minimizing the manual handling of base conversion operations.

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

The given Python code provides a solution for converting a decimal number to its base-9 equivalent. The class Solution contains the function baseNineConverter, which takes an integer number as its parameter. This function iteratively determines the base-9 representation by performing the following steps:

  • Initialize an empty string result to store the base-9 number.
  • Use a while loop to process the decimal number until the value becomes zero.
  • Within the loop, prepend the remainder of the division of number by 9 to result.
  • Update the number itself by performing integer division by 9.
  • After the loop ends, convert the result string back to an integer and return it.

This conversion is useful in scenarios where numbers need to be represented in a non-standard numeric base such as base-9. The code efficiently handles this transformation, ensuring each digit of the input decimal number is properly converted to its base-9 counterpart.

Comments

No comments yet.