@donggua_fu

It's the first time I saw this kind of radix problem, it also feels to be like a magic. Here is my thought:

Given a sorted array of numbers in base-10: 1, 2, 3, 4, ... Since each number that contains 9 was excluded, the only possible numbers left are 0-8, looks like 9-based right ? But are they in ascending order and increment by one ? The answer is fortunately yes !

Because:

1, Every possible number n expressed in 9-based are in the sequence of '1', '2', '3', '4', ... since this sequence already exhausts every possibility of number combinations using 0-8

2, Since this sequence is in ascending order in 10-based expression, it must be in ascending order in 9-based expression. Why ? Think of how you compare two numbers intuitively in 10-based situation: 100 > 99 because 100 has more digits, 98>97 because 9==9, and 8>7. This also applies to any n-based number system including 9-based.

Since every possible number in 9-based system presents in the sequence after you "remove-9" and they are in ascending order, they must be exactly incrementing one by one in 9-based system.

Now, forget about "removing 9", just write down the ascending sequence in 9-based system:

'1' ,'2',...'8', '10','11','12'... ->9 based

The related ordering would be

1, 2, ... 8, 9, 10, 11,...

Given an input number n, you just convert it into 9-based, for example, convert 2->'2', 9->'10', 10->'11', 11->'12'. That converted number if you look at it in 10-based system is the output