Is Remove 9 easy or hard?

Remove 9 is labeled Hard because the trick is recognizing the base-9 relationship. The implementation itself is short, but the insight that skipping digit 9 turns the sequence into base-9 numbering is not immediately obvious.

Remove 9 Python/Java solution

Most implementations convert n into base 9 using repeated division and remainder operations. The same logic works in Python, Java, C++, and Go. Each iteration extracts a digit with n % 9 and reduces n using integer division by 9.

How to solve Remove 9 in O(log n)?

Use base-9 conversion. Repeatedly divide n by 9 and append the remainder (n % 9) as the next digit of the answer. Continue until n becomes zero. The resulting digits form the number that corresponds to the nth positive integer without digit 9.

What is the best approach for Remove 9?

The best approach converts the given number n into base 9. Since valid numbers cannot contain digit 9, the allowed digits are 0–8, which corresponds exactly to a base-9 numbering system. Converting n to base 9 directly produces the nth number without digit 9. This runs in O(log n) time and O(1) space.

Is Remove 9 asked at Google/Amazon/Meta?

Remove 9 represents a classic math and number-system transformation problem. Variants of digit-restriction or base-conversion questions have appeared in interviews at companies like Google and Amazon because they test mathematical insight rather than brute-force coding.

What data structure is used in Remove 9?

No complex data structure is required. The optimal solution relies purely on arithmetic operations and base conversion logic. Some implementations temporarily store digits while building the result, but the algorithm mainly uses math operations.

What is the time complexity of Remove 9?

The optimal base-9 conversion solution runs in O(log n) time because each step divides the number by 9. Only a few iterations equal to the number of digits in base 9 are required. Space complexity remains O(1) since the result is built using simple arithmetic operations.

Description Video 16:56

660. Remove 9

Hard57.3% acceptance1 companyPremium elsewhere, free here

Start from integer 1, remove any integer that contains 9 such as 9, 19, 29...

Now, you will have a new integer sequence [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, ...].

Given an integer n, return the n^th (1-indexed) integer in the new sequence.

Example 1:

Input: n = 9
Output: 10

Example 2:

Input: n = 10
Output: 11

Constraints:

1 <= n <= 8 * 10⁸

Asked at 1 company

Houzz

Topics

Math

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

Your code is saved on this device.