We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Remove 9

Number: 660

Difficulty: Hard

Paid? Yes

Companies: Houzz

Problem Description

Given an integer n, find the nth (1-indexed) number in the sequence of positive integers that do not contain the digit '9'. The sequence is formed by starting at 1 and skipping any number that includes a '9', e.g., 9, 19, 29, etc.

Key Insights

  • Recognize that numbers without the digit '9' can be mapped to a numbering system with only 9 digits, essentially a base 9 system.
  • Converting n to its base 9 representation yields a digit sequence that, interpreted in base 10, produces the nth number in the desired sequence.
  • The conversion uses repeated division and modular arithmetic to build the base 9 representation.
  • This method is both time and space efficient, suitable for large inputs.

Space and Time Complexity

Time Complexity: O(log n) since the conversion to base 9 requires roughly log₉(n) iterations.
Space Complexity: O(log n) for storing the digits of the base 9 representation.

Solution

The solution involves converting n into its base 9 representation by continuously dividing n by 9 and taking the remainders. These remainders form the digits (in reverse order) of the base 9 number. Reversing this sequence gives the correct order and, when interpreted as a decimal number, yields the nth number in the sequence of numbers that do not contain the digit '9'. This approach cleverly bypasses the need to iterate through each number and check for the presence of the digit '9'.

Code Solutions

# Function to return the nth number that does not contain the digit 9
def remove_nine(n):
    digits = []
    # Convert n into its base 9 representation
    while n:
        n, remainder = divmod(n, 9)
        digits.append(str(remainder))
    # Reverse the digits to form the correct number order and convert to integer
    return int(''.join(digits[::-1]))

# Example usage:
if __name__ == '__main__':
    n = 10
    print(remove_nine(n))  # Expected output: 11
← Back to All Questions