Algorithm (Math)

1. The process of stripping out the 9 is equivalent to finding the 9-ary representation of the number $n$.

Code

class Solution {
 public:
  int newInteger(int n) {

    function<int(int, int)> to_n_ary = [&] (int x, int base) {
      if (x == 0)
        return 0;
      else
        return x % base + 10 * to_n_ary(x / base, base);
    };

    return to_n_ary(n, 9);
  }
};