Remove 9
Problem
If you list non-negative integers and remove any containing the digit 9, return the n-th remaining.
n = 910def new_integer(n):
out = 0; place = 1
while n:
out += (n % 9) * place; n //= 9; place *= 10
return outfunction newInteger(n) {
let out = 0, place = 1;
while (n) { out += (n % 9) * place; n = Math.floor(n / 9); place *= 10; }
return out;
}int newInteger(int n) {
int out = 0, place = 1;
while (n > 0) { out += (n % 9) * place; n /= 9; place *= 10; }
return out;
}int newInteger(int n) {
int out = 0, place = 1;
while (n > 0) { out += (n % 9) * place; n /= 9; place *= 10; }
return out;
}Explanation
If we throw away every number containing the digit 9, the survivors use only the digits 0 through 8 — that is exactly nine allowed digits. So the list of survivors behaves just like counting in base 9.
That means the n-th survivor is simply n written in base 9, but then read as if it were a normal base-10 number.
The code does this digit by digit. It repeatedly takes n % 9 (the next base-9 digit), places it into the next decimal slot with place (which is 1, then 10, then 100, ...), and shrinks n with n //= 9. Building the result with powers of 10 is what re-reads the base-9 digits as base-10.
Example: n = 9. In base 9 that is "10" (one nine, zero ones). Read as base 10 it is 10, which matches: skipping 9, the 9th surviving number is indeed 10.
Since each step divides n by 9, only about log n steps are needed.