Remove 9 - Solution & Explanation

Problem Overview: You are given an integer n. Return the nth positive integer that does not contain the digit 9. Instead of generating all numbers and filtering, the key observation is that numbers without digit 9 behave like a base-9 numbering system.

Approach 1: Brute Force Enumeration (O(n log n) time, O(1) space)

The straightforward solution is to iterate through positive integers and count how many do not contain the digit 9. For each number, repeatedly extract digits using modulo and division to check if any digit equals 9. If the number is valid, increment the counter until it reaches n. This works but becomes slow as n grows because many numbers must be checked and discarded. Each validation requires scanning digits, giving roughly O(log x) work per number where x is the current candidate. This approach mainly demonstrates the problem constraints but rarely passes strict performance expectations.

Approach 2: Base-9 Conversion (O(log n) time, O(1) space)

The optimal solution relies on a mathematical insight. If digit 9 is forbidden, every valid number only uses digits 0–8. That means the sequence of valid numbers behaves exactly like numbers written in base 9. Instead of skipping numbers containing 9, convert n directly into base 9. The digits of this base-9 representation form the answer when interpreted as a normal decimal number. Implementation is simple: repeatedly divide n by 9, append n % 9 as the next digit, and build the result. This avoids checking any invalid numbers and jumps directly to the correct value.

This trick works because counting without the digit 9 reduces the digit choices from 10 to 9. The mapping between sequence index and value becomes identical to base-9 numbering. Problems like this commonly appear in math and base conversion patterns where digit constraints change the effective number system.

Recommended for interviews: The base-9 conversion approach is what interviewers expect. Mentioning the brute force approach first shows you understand the requirement, but recognizing the digit restriction as a base conversion problem demonstrates stronger algorithmic insight. This pattern often appears in math and number theory style questions where counting rules alter the number system.