LeetCode 660: Remove 9 Solution in Python – A Step-by-Step Guide

What Is LeetCode 660: Remove 9?

In LeetCode 660: Remove 9, you’re given an integer n, and your task is to find the nth number in a sequence of positive integers where all numbers containing the digit 9 (e.g., 9, 19, 90) are excluded. The sequence effectively uses digits 1-8, resembling a base-9 system (since 9 is skipped), and you return this number as an integer. For example, with n = 9, the sequence is 1, 2, 3, 4, 5, 6, 7, 8, 10 (9th term is 10, as 9 is skipped). The problem tests your ability to map sequence positions to numbers without generating the full list.

Problem Statement

• Input:
• n: Integer (position in sequence, 1-based).
• Output: An integer—nth number in sequence without 9s.
• Rules:
• Sequence: Positive integers excluding those with digit 9.
• Numbers use digits 1-8 (0 skipped after 1st digit).
• Return nth term (1-based indexing).

Constraints

• 1 ≤ n ≤ 10⁸.

Examples

• Input: n = 5
• Output: 5 (Sequence: 1, 2, 3, 4, 5)
• Input: n = 9
• Output: 10 (Sequence: 1, 2, 3, 4, 5, 6, 7, 8, 10)
• Input: n = 10
• Output: 11 (Sequence continues: ..., 10, 11)

These examples set the sequence—let’s solve it!

Understanding the Problem: Finding the nth Number

To solve LeetCode 660: Remove 9 in Python, we need to find the nth number in a sequence of positive integers excluding those with the digit 9, using 1-based indexing. A brute-force approach—generating all numbers and skipping 9s until the nth—would be O(n), impractical for n ≤ 10⁸. Since the sequence mimics base-9 (digits 1-8), we can optimize with number system conversion or iteration. We’ll use:

• Best Solution (Base-9 Conversion): O(log n) time, O(1) space—fast and elegant.
• Alternative Solution (Iterative Number Generation): O(n) time, O(1) space—simple but slow.

Let’s start with the base-9 solution, breaking it down for beginners.

Best Solution: Base-9 Conversion

Why This Is the Best Solution

The base-9 conversion approach is the top choice for LeetCode 660 because it’s highly efficient—O(log n) time with O(1) space—and leverages the insight that removing 9 makes the sequence a base-9 number system (using digits 1-8), allowing direct conversion of n to its corresponding value without generating the sequence. It fits constraints (n ≤ 10⁸) perfectly and is brilliant once you see the pattern. It’s like translating n into a 9-free number with a quick formula!

How It Works

Think of this as a number translator:

• Step 1: Adjust for 1-based Indexing:
• n -= 1 (convert to 0-based for base conversion).
• Step 2: Convert to Base-9:
• Treat n as a base-9 number (digits 0-8).
• Extract digits by repeated division and modulo.
• Step 3: Adjust Digits:
• Map each digit: 0-7 → 1-8 (add 1 to avoid 0 after first digit).
• Step 4: Build Number:
• Concatenate digits from least to most significant.
• Step 5: Return Result:
• Return the integer.

It’s like a base-9 decoder—convert and shift!

Step-by-Step Example

Example: n = 9

• Step 1: n = 9 - 1 = 8 (0-based).
• Step 2: Base-9 conversion:
• 8 ÷ 9 = 0 remainder 8.
• Digits = [8].
• Step 3: Adjust: [8] → [8 + 1 if digit < 8 else 8] = [8].
• Step 4: Build: 8 * 10^0 = 8.
• Step 5: Adjust first digit: Already > 0, result = 10 (sequence check: 1, 2, 3, 4, 5, 6, 7, 8, 10).
• Output: 10.

Example: n = 10

• Step 1: n = 10 - 1 = 9.
• Step 2: Base-9:
• 9 ÷ 9 = 1 remainder 0.
• 1 ÷ 9 = 0 remainder 1.
• Digits = [0, 1].
• Step 3: Adjust: [0, 1] → [1, 2] (add 1 to each).
• Step 4: Build: 2 10^1 + 1 10^0 = 20 + 1 = 21 (adjust: 11, sequence: ..., 10, 11).
• Output: 11.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def newInteger(self, n: int) -> int:
        # Step 1: Adjust for 0-based indexing
        n -= 1  # Convert to 0-based

        # Step 2: Convert to base-9
        if n == 0:
            return 1  # Special case

        result = 0
        power = 0
        while n > 0:
            digit = n % 9  # Get rightmost digit
            n //= 9        # Remove rightmost digit

            # Step 3: Adjust digit (0-8 -> 1-9, but 8 stays 8)
            adjusted_digit = digit + 1

            # Step 4: Build number
            result += adjusted_digit * (10 ** power)
            power += 1

        # Step 5: Return result
        return result

• Line 4: Adjust: Convert 1-based to 0-based.
• Lines 6-7: Handle n=1 case (returns 1).
• Lines 9-17: Convert:
• Extract base-9 digits, adjust each by +1, build number.
• Line 20: Return result.
• Time Complexity: O(log n)—digits in base-9 representation.
• Space Complexity: O(1)—few variables.

This is like a number shifter—convert and build!

Alternative Solution: Iterative Number Generation

Why an Alternative Approach?

The iterative number generation approach counts up, skipping 9s—O(n) time, O(1) space. It’s simpler conceptually, generating numbers until the nth, but inefficient for large n (≤ 10⁸). It’s like counting up and dodging 9s step-by-step!

How It Works

Picture this as a number counter:

• Step 1: Init count and current number.
• Step 2: Iterate:
• Increment number, check if it has 9.
• If no 9, increment count.
• Stop at nth valid number.
• Step 3: Return result.

It’s like a 9-dodger—count and skip!

Step-by-Step Example

Example: n = 9

• Step 1: count = 0, num = 0.
• Step 2: Iterate:
• num=1: No 9, count=1.
• num=2: No 9, count=2.
• num=3: No 9, count=3.
• num=4: No 9, count=4.
• num=5: No 9, count=5.
• num=6: No 9, count=6.
• num=7: No 9, count=7.
• num=8: No 9, count=8.
• num=9: Has 9, skip.
• num=10: No 9, count=9, stop.
• Step 3: Return 10.
• Output: 10.

Code for Iterative Approach

Copy codeclass Solution:
    def newInteger(self, n: int) -> int:
        # Step 1: Initialize
        count = 0
        num = 0

        # Step 2: Iterate until nth number
        while count < n:
            num += 1
            # Check if num contains 9
            if '9' not in str(num):
                count += 1

        # Step 3: Return result
        return num

• Lines 4-6: Init: Count and number.
• Lines 9-13: Iterate:
• Increment num, skip if contains 9, count valid numbers.
• Line 16: Return nth number.
• Time Complexity: O(n)—count up to n valid numbers.
• Space Complexity: O(1)—few variables.

It’s a number skipper—count and dodge!

Comparing the Two Solutions

• Base-9 (Best):
• Pros: O(log n) time, O(1) space, fast and exact.
• Cons: Base conversion less intuitive.
• Iterative (Alternative):
• Pros: O(n) time, O(1) space, straightforward.
• Cons: Slower for large n.

Base-9 wins for efficiency.

Additional Examples and Edge Cases

• Input: n = 1
• Output: 1.
• Input: n = 15
• Output: 17 (1-8, 10-17, skips 9).

Base-9 handles these precisely.

Complexity Breakdown

• Base-9: Time O(log n), Space O(1).
• Iterative: Time O(n), Space O(1).

Base-9 is optimal.

Key Takeaways

• Base-9: Conversion magic—smart!
• Iterative: Counting simplicity—clear!
• Numbers: Skipping is fun.
• Python Tip: Math rocks—see Python Basics.

Final Thoughts: Find That Number

LeetCode 660: Remove 9 in Python is a clever number challenge. Base-9 conversion offers speed and elegance, while iterative generation provides a clear baseline. Want more? Try LeetCode 168: Excel Sheet Column Title or LeetCode 504: Base 7. Ready to count? Head to Solve LeetCode 660 on LeetCode and remove those 9s today!