Es una pregunta de entrevista.

Dado un número n, averigüe cuántos números tienen el dígito 2 en el rango 0 ... n

Por ejemplo ,

entrada = 13 salida = 2 (2 y 12)

Di la solución habitual de O (n ^ 2) pero hay un mejor enfoque.

¿Existe alguna fórmula de 'truco' que me ayude a obtener la respuesta de inmediato?