Es muy fácil si tienes en cuenta que los rangos tipo 100->199, 2000->2999, etc son inmediatos de calcular. Sólo tienes que dividir el rango que te piden en subrangos así y se resuelve en un momento.

Puedes calcular previamente cuantas veces aparece cada dígito para rangos de tamaño 1, 10, 100, 1000, ..., 100000000. Y luego con eso precalculado hacer algo así.

Adjunto el código en ANSI C. Renombrar a 4808.c.

gcc -Wall -ansi 4808.c -o 4808