algorithm - number - Recuento de ocurrencias de dígitos

java long digits

Question

Este problema realmente me está confundiendo; nos dan dos enteros A , B , queremos contar las ocurrencias de dígitos en el rango [A, B] . Pensé que si pudiéramos contar el número de ocurrencias de dígitos en el rango [0, A] y [0, B] , el resto es trivial. Entonces, ¿cómo puedo contar las ocurrencias de dígitos en un rango [0, x] ? Esto no es tarea, este es realmente un problema de SPOJ. El enfoque ingenuo no funcionará, ya que A y B pueden ser tan grandes como 10 ^ 9. Aquí hay algunos ejemplos:

Entrada:

1 10

Salida:

1 2 1 1 1 1 1 1 1 1

Entrada:

44 497

Salida:

85 185 185 185 190 96 96 96 95 93

Answer 1

Con problemas de este tipo, a menudo es útil comenzar con una implementación lenta y fea antes de resolver cómo hacerlo de manera correcta y rápida. Puede aprender algo sobre la estructura del problema, y ​​puede usar la implementación lenta para probar la corrección de la rápida.

En Python, por ejemplo, puede escribir la versión lenta de esta manera (no es necesariamente la mejor manera de hacerlo, pero está entre las más cortas ...)

>>> A, B = 1, 100
>>> from collections import Counter
>>> Counter(''''.join(map(str, range(A, B + 1))))
Counter({''1'': 21, ''3'': 20, ''2'': 20, ''5'': 20, ''4'': 20,
''7'': 20, ''6'': 20, ''9'': 20, ''8'': 20, ''0'': 11})

Answer 2

Primero probaría el enfoque de la fuerza bruta para que algo funcione. Mire cada número, itere a través de cada carácter en la representación de cadena de ese número, etc.

Sin embargo, hay una manera más fácil.

• En el intervalo [0,9], 3 aparece 1 vez
• En el intervalo [0,99], 3 aparece 10 veces en el primer dígito y 10 veces en el segundo dígito
• En el intervalo [0,999], 3 aparece 100 veces en el primer dígito, 100 veces en el segundo dígito y 100 veces en el tercer dígito.

Puede generalizar esto y, con un poco de esfuerzo, proponer una fórmula para ver cuántos de un cierto dígito (0 es un posible caso especial) aparecerán en un cierto rango. No es necesario que revises cada número.

Answer 3

Wolfram Alpha es tu amigo (al menos en algún número cerca de 21 * 10 ^ 4):

Input:
44 497
Output:
85 185 185 185 190 96 96 96 95 93

Pruébame

Resultado:

{85, 185, 185, 185, 188, 96, 96, 96, 95, 93}