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:

1
2

Input: n = 9
Output: 10

Example 2:

1
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int newInteger(int n) {
        int ans = 0, mul = 1;
        while (n) {
            ans += (n % 9) * mul;
            n /= 9;
            mul *= 10;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9

func newInteger(n int) int {
    ans, mul := 0, 1
    for n > 0 {
        ans += (n % 9) * mul
        n /= 9
        mul *= 10
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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
    }
}
1
2
3
4
5
6
7
8
9

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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.