This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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

So now, you will have a new integer sequence: 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, ...

Given a positive integer `n`

, you need to return the n-th integer after removing. Note that 1 will be the first integer.

**Example 1:**

Input:9Output:10

** Hint**: n will not exceed `9 x 10^8`

.

b'

\n

\n#### Approach #1: Mathematical

\n\n

\n

'
\n\n

\n\n

**Intuition**

Let\'s write the first numbers and try to notice a pattern. Those numbers are:

\n1, 2, 3, 4, 5, 6, 7, 8,\n10, 11, 12, 13, 14, 15, 16, 17, 18,\n20, 21, 22, 23, 24, 25, 26, 27, 28,\n...\n80, 81, 82, 83, 84, 85, 86, 87, 88,\n100, 101, 102, ...\n

These numbers look exactly like all base-9 numbers!

\nIndeed, every base-9 number is a number in this sequence, and every number in this sequence is a base-9 number. Both this sequence and the sequence of all base-9 numbers are in increasing order. The answer is therefore just the n-th base-9 number.

\n\n**Complexity Analysis**

- \n
- \n
Time Complexity: , since has at most 9 digits.

\n \n - \n
Space Complexity: .

\n \n

\n

Analysis written by: @awice.

\n