problemhardalgorithmsleetcode-660leetcode 660leetcode660

Remove 9

HardUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

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 nth (1-indexed) integer in the new sequence.

Examples

Example 1:

Input: n = 9
Output: 10

Example 2:

Input: n = 10
Output: 11

Constraints:

  • 1 <= n <= 8 * 10^8

Solution

Method 1 – Base 9 Conversion

Intuition

If we remove all numbers containing the digit 9, the sequence of valid numbers is exactly the sequence of numbers written in base 9, but interpreted as decimal. For example, the 9th number in base 9 is 10 (decimal 9), which is 10 in the new sequence.

Approach

  1. Convert n to its base 9 representation.
  2. Interpret the base 9 digits as a decimal number.
  3. This gives the nth number in the sequence without any digit 9.

Code

C++
class Solution {
public:
    int newInteger(int n) {
        int ans = 0, mul = 1;
        while (n) {
            ans += (n % 9) * mul;
            n /= 9;
            mul *= 10;
        }
        return ans;
    }
};
Go
func newInteger(n int) int {
    ans, mul := 0, 1
    for n > 0 {
        ans += (n % 9) * mul
        n /= 9
        mul *= 10
    }
    return ans
}
Java
class Solution {
    public int newInteger(int n) {
        int ans = 0, mul = 1;
        while (n > 0) {
            ans += (n % 9) * mul;
            n /= 9;
            mul *= 10;
        }
        return ans;
    }
}
Kotlin
class Solution {
    fun newInteger(n: Int): Int {
        var n = n
        var ans = 0
        var mul = 1
        while (n > 0) {
            ans += (n % 9) * mul
            n /= 9
            mul *= 10
        }
        return ans
    }
}
Python
class Solution:
    def newInteger(self, n: int) -> int:
        ans = 0
        mul = 1
        while n > 0:
            ans += (n % 9) * mul
            n //= 9
            mul *= 10
        return ans
Rust
impl Solution {
    pub fn new_integer(mut n: i32) -> i32 {
        let mut ans = 0;
        let mut mul = 1;
        while n > 0 {
            ans += (n % 9) * mul;
            n /= 9;
            mul *= 10;
        }
        ans
    }
}
TypeScript
class Solution {
    newInteger(n: number): number {
        let ans = 0, mul = 1;
        while (n > 0) {
            ans += (n % 9) * mul;
            n = Math.floor(n / 9);
            mul *= 10;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(log_9 n), since we process each digit in base 9.
  • 🧺 Space complexity: O(1), as only a few variables are used.

Comments