É uma questão de entrevista.

Dado um número n, descubra quantos números têm o dígito 2 no intervalo 0 ... n

Por exemplo ,

entrada = 13 saída = 2 (2 e 12)

Eu dei a solução usual O (n ^ 2), mas há uma abordagem melhor.

Existe alguma fórmula 'truque' que me ajudará a obter a resposta imediatamente?