LC 660. Remove 9 【lock, hard】

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: 9

Output: 10

Hint: n will not exceed 9 x 10^8.

找规律题。借鉴网上的思路。

1，2，3，4，5，6，7，8，10，。。。，18，20，。。。28，30

把9拿掉以后，可以把它看成一个九进制的序列。也就是说，9进制中的数字n如果把它当作10进制来看，就是在这个序列中的第n个。

class Solution {

public:

    int newInteger(int n) {

        int base = ;

        int ans = ;

        while(n != ){

            ans = ans + (n % ) * base;

            n /= ;

            base *= ;

        }

        return ans;

    }

};