Remove 9

Remove 9

What is this problem about?

The Remove 9 problem asks: if you write positive integers excluding any containing the digit 9, find the n-th number in this sequence. The sequence is 1,2,3,4,5,6,7,8,10,11,...,18,20,... This hard coding problem recognizes the sequence as base-9 counting. The math interview pattern is demonstrated.

Why is this asked in interviews?

Houzz asks this because recognizing "numbers without digit 9" as base-9 numbers is a non-obvious but elegant mathematical insight. It tests the ability to see number sequence patterns.

Algorithmic pattern used

Base-9 conversion. The sequence 1,2,...,8,10,...,18,... is exactly the base-9 numbers. The n-th number (1-indexed) = the decimal representation of n written in base 9. For example: n=9 → base9 = "10" → decimal 10 (the 9th number in sequence is 10, which uses no '9').

Example explanation

n=9. Convert 9 to base 9: 9 = 1×9 + 0 = "10" → decimal 10. n=10 → 10 in base 9 = "11" → 11. n=81 → 81 in base 9 = "100" → 100. Return int(str(n, base=9_representation)) = n written as if its base-9 digits are a base-10 number.

Common mistakes candidates make

• Trying to enumerate and skip numbers with '9' (too slow for large n).
• Not recognizing the base-9 pattern.
• Converting in wrong direction (should convert n to base-9 digits, then read as decimal).
• Off-by-one (sequence starts at 1, not 0).

Interview preparation tip

Remove 9 is a beautiful mathematical reframing: "skip numbers with digit 9" = "count in base 9." The digits 0-8 become our counting symbols; '9' never appears. The n-th element of the sequence = number n represented in base 9, interpreted as a decimal. Recognize base-change patterns in number sequences — they often reveal elegant O(log n) solutions.