algorithm - tiene - que son números binarios

¿Cómo contar cada dígito en un rango de números enteros?

Question

Imagine que vende esos dígitos metálicos utilizados para numerar casas, puertas de casilleros, habitaciones de hoteles, etc. Necesita encontrar cuántos de cada dígito enviar cuando su cliente necesita numerar puertas / casas:

• 1 a 100
• 51 a 300
• 1 a 2.000 con ceros a la izquierda

La solución obvia es hacer un ciclo desde el primero hasta el último número, convertir el contador en una cadena con o sin ceros a la izquierda, extraer cada dígito y usarlo como índice para incrementar una matriz de 10 enteros.

Me pregunto si hay una mejor manera de resolver esto, sin tener que recorrer todo el rango de enteros.

Las soluciones en cualquier idioma o pseudocódigo son bienvenidas.

Editar:

Respuestas revisión
John en CashCommons y Wayne Conrad comentan que mi enfoque actual es lo suficientemente bueno y rápido. Permítanme usar una analogía tonta: si te dieron la tarea de contar los cuadrados en un tablero de ajedrez en menos de 1 minuto, puedes terminar la tarea contando los cuadrados uno por uno, pero una mejor solución es contar los lados y haz una multiplicación, porque más tarde se te pedirá que cuentes las fichas en un edificio.
Alex Reisner señala una ley matemática muy interesante que, desafortunadamente, no parece ser relevante para este problema.
Andrés sugiere el mismo algoritmo que estoy usando, pero extrae dígitos con% 10 operaciones en lugar de subcadenas.
John en CashCommons y phord proponen el cálculo previo de los dígitos requeridos y su almacenamiento en una tabla de búsqueda o, para velocidad bruta, una matriz. Esta podría ser una buena solución si tuviéramos un valor absoluto, inamovible, en piedra, valor entero máximo. Nunca he visto uno de esos.
High-Performance Mark y colador calcularon los dígitos necesarios para varios rangos. El resultado de un millón parece indicar que hay una proporción, pero los resultados para el otro número muestran proporciones diferentes.
colador encontró algunas fórmulas que pueden usarse para contar un dígito para un número que es una potencia de diez. Robert Harvey tuvo una experiencia muy interesante al publicar la pregunta en MathOverflow. Uno de los chicos de matemáticas escribió una solución usando notación matemática.
Aaronaught desarrolló y probó una solución usando matemáticas. Después de publicarlo, revisó las fórmulas originadas en Math Overflow y encontró un error en él (apunte a Stackoverflow :).
noahlavine desarrolló un algoritmo y lo presentó en pseudocódigo.

Una nueva solución
Después de leer todas las respuestas y hacer algunos experimentos, encontré que para un rango de entero de 1 a 10 ⁿ -1:

• Para los dígitos 1 a 9, se necesitan n * 10 ^(n-1) piezas
• Para el dígito 0, si no se utilizan ceros a la izquierda, se necesitan n * 10 ^n-1 - ((10 ⁿ -1) / 9)
• Para el dígito 0, si usa ceros a la izquierda, se necesitan n * 10 ^n-1 - n

La primera fórmula fue encontrada por colador (y probablemente por otros), y encontré las otras dos por prueba y error (pero pueden incluirse en otras respuestas).

Por ejemplo, si n = 6, el rango es de 1 a 999.999:

• Para los dígitos del 1 al 9, necesitamos 6 * 10 ⁵ = 600,000 de cada uno
• Para el dígito 0, sin los ceros a la izquierda, necesitamos 6 * 10 ⁵ - (10 ⁶ -1) / 9 = 600,000 - 111,111 = 488,889
• Para el dígito 0, con ceros a la izquierda, necesitamos 6 * 10 ⁵ - 6 = 599,994

Estos números se pueden verificar usando resultados de Marca de Alto Rendimiento .

Usando estas fórmulas, mejoré el algoritmo original. Todavía sigue desde el primer hasta el último número en el rango de enteros, pero, si encuentra un número que es una potencia de diez, usa las fórmulas para agregar a los dígitos cuente la cantidad para un rango completo de 1 a 9 o 1 a 99 o 1 a 999 etc. Aquí está el algoritmo en pseudocódigo:

integer First,Last //First and last number in the range integer Number //Current number in the loop integer Power //Power is the n in 10^n in the formulas integer Nines //Nines is the resut of 10^n - 1, 10^5 - 1 = 99999 integer Prefix //First digits in a number. For 14,200, prefix is 142 array 0..9 Digits //Will hold the count for all the digits FOR Number = First TO Last CALL TallyDigitsForOneNumber WITH Number,1 //Tally the count of each digit //in the number, increment by 1 //Start of optimization. Comments are for Number = 1,000 and Last = 8,000. Power = Zeros at the end of number //For 1,000, Power = 3 IF Power > 0 //The number ends in 0 00 000 etc Nines = 10^Power-1 //Nines = 10^3 - 1 = 1000 - 1 = 999 IF Number+Nines <= Last //If 1,000+999 < 8,000, add a full set Digits[0-9] += Power*10^(Power-1) //Add 3*10^(3-1) = 300 to digits 0 to 9 Digits[0] -= -Power //Adjust digit 0 (leading zeros formula) Prefix = First digits of Number //For 1000, prefix is 1 CALL TallyDigitsForOneNumber WITH Prefix,Nines //Tally the count of each //digit in prefix, //increment by 999 Number += Nines //Increment the loop counter 999 cycles ENDIF ENDIF //End of optimization ENDFOR SUBROUTINE TallyDigitsForOneNumber PARAMS Number,Count REPEAT Digits [ Number % 10 ] += Count Number = Number / 10 UNTIL Number = 0

Por ejemplo, para el rango 786 a 3,021, el contador se incrementará:

• Por 1 de 786 a 790 (5 ciclos)
• Por 9 de 790 a 799 (1 ciclo)
• Por 1 de 799 a 800
• Por 99 de 800 a 899
• Por 1 de 899 a 900
• Por 99 de 900 a 999
• Por 1 de 999 a 1000
• Por 999 de 1000 a 1999
• Por 1 de 1999 a 2000
• Por 999 de 2000 a 2999
• Por 1 de 2999 a 3000
• Por 1 de 3000 a 3010 (10 ciclos)
• Por 9 de 3010 a 3019 (1 ciclo)
• Por 1 de 3019 a 3021 (2 ciclos)

Total: 28 ciclos Sin optimización: 2,235 ciclos

Tenga en cuenta que este algoritmo resuelve el problema sin ceros a la izquierda. Para usarlo con ceros a la izquierda, utilicé un truco:

Si se necesita un rango de 700 a 1,000 con ceros a la izquierda, use el algoritmo de 10,700 a 11,000 y luego sustraiga 1,000 - 700 = 300 del recuento del dígito 1.

Punto de referencia y código fuente

Probé el enfoque original, el mismo enfoque usando% 10 y la nueva solución para algunos rangos grandes, con estos resultados:

Original 104.78 seconds With %10 83.66 With Powers of Ten 0.07

Una captura de pantalla de la aplicación de referencia:
texto alternativo http://clarion.sca.mx/images/stories/digitsbench.png

Si desea ver el código fuente completo o ejecutar el punto de referencia, use estos enlaces:

• Código fuente completo (en Clarion ): http://sca.mx/ftp/countdigits.txt
• Proyecto compilable y win32 exe: http://sca.mx/ftp/countdigits.zip

Respuesta aceptada

la solución de noahlavine puede ser correcta, pero simplemente no pude seguir el pseudo código, creo que faltan algunos detalles o no están completamente explicados.

La solución de Aaronaught parece ser correcta, pero el código es demasiado complejo para mi gusto.

Acepté la respuesta de filtro , porque su línea de pensamiento me guió para desarrollar esta nueva solución.

Answer 1

Aquí hay una muy mala respuesta, me da vergüenza publicarlo. Le pedí a Mathematica que calcule los dígitos usados ​​en todos los números de 1 a 1,000,000, sin tener 0''s. Esto es lo que obtuve:

0   488895
1   600001
2   600000
3   600000
4   600000
5   600000
6   600000
7   600000
8   600000
9   600000

La próxima vez que ordene dígitos adhesivos para vender en su ferretería, ordene en estas proporciones, no estará muy equivocado.

Answer 2

Esto no responde a su pregunta exacta, pero es interesante observar la distribución de los primeros dígitos según la Ley de Benford . Por ejemplo, si eliges un conjunto de números al azar, el 30% de ellos comenzará con "1", lo que es un poco contrario a la intuición.

No conozco ninguna distribución que describa dígitos posteriores, pero es posible que pueda determinar esto empíricamente y proponer una fórmula simple para calcular una cantidad aproximada de dígitos requeridos para cualquier rango de números.

Answer 3

Hay una solución matemática clara para un problema como este. Supongamos que el valor no tiene relleno para la cantidad máxima de dígitos (no lo es, pero lo compensaremos más adelante) y razonar a través de él:

• De 0 a 9, cada dígito aparece una vez
• De 0 a 99, cada dígito se produce 20 veces (10 veces en la posición 1 y 10 veces en la posición 2)
• De 0 a 999, cada dígito se produce 300 veces (100x en P1, 100x en P2, 100x en P3)

El patrón obvio para cualquier dígito dado, si el rango es de 0 a una potencia de 10, es N * 10 ^N-1 , donde N es la potencia de 10.

¿Qué pasa si el rango no es una potencia de 10? Comience con la potencia más baja de 10, luego haga ejercicio. El caso más fácil de tratar es un máximo como 399. Sabemos que por cada múltiplo de 100, cada dígito aparece al menos 20 veces, pero tenemos que compensar el número de veces que aparece en la posición del dígito más significativo, que va a ser exactamente 100 para los dígitos 0-3, y exactamente cero para todos los demás dígitos. Específicamente, la cantidad extra para agregar es 10 ^N para los dígitos relevantes.

Poniendo esto en una fórmula, para los límites superiores que son 1 menos que un múltiplo de una potencia de 10 (es decir, 399, 6999, etc.) se convierte en: M * N * 10 ^N-1 + iif (d <= M, 10 ^N , 0)

Ahora solo tiene que lidiar con el resto (que llamaremos R ). Tome 445 como ejemplo. Este es el resultado que sea para 399, más el rango 400-445. En este rango, el MSD ocurre R más veces, y todos los dígitos (incluido el MSD) también ocurren en las mismas frecuencias que lo harían desde el rango [0 - R ].

Ahora solo tenemos que compensar los ceros iniciales. Este patrón es fácil, es solo:

10 ^N + 10 ^N-1 + 10 ^N-2 + ... + ** 10 ⁰

Actualización: esta versión tiene en cuenta correctamente los "ceros de relleno", es decir, los ceros en las posiciones medias cuando se trata del resto ([4 0 0, 4 0 1, 4 0 2, ...]). Averiguar los ceros de relleno es un poco feo, pero el código revisado (pseudocódigo de estilo C) lo maneja:

function countdigits(int d, int low, int high) {
    return countdigits(d, low, high, false);
}

function countdigits(int d, int low, int high, bool inner) {
    if (high == 0)
        return (d == 0) ? 1 : 0;

    if (low > 0)
        return countdigits(d, 0, high) - countdigits(d, 0, low);

    int n = floor(log10(high));
    int m = floor((high + 1) / pow(10, n));
    int r = high - m * pow(10, n);
    return
        (max(m, 1) * n * pow(10, n-1)) +                             // (1)
        ((d < m) ? pow(10, n) : 0) +                                 // (2)
        (((r >= 0) && (n > 0)) ? countdigits(d, 0, r, true) : 0) +   // (3)
        (((r >= 0) && (d == m)) ? (r + 1) : 0) +                     // (4)
        (((r >= 0) && (d == 0)) ? countpaddingzeros(n, r) : 0) -     // (5)
        (((d == 0) && !inner) ? countleadingzeros(n) : 0);           // (6)
}

function countleadingzeros(int n) {
      int tmp= 0;
      do{
         tmp= pow(10, n)+tmp;
         --n;
         }while(n>0);
         return tmp;
         }

function countpaddingzeros(int n, int r) {
    return (r + 1) * max(0, n - max(0, floor(log10(r))) - 1);
}

Como puede ver, se ha vuelto un poco más feo, pero todavía se ejecuta en el tiempo O (log n), por lo que si necesita manejar números en los miles de millones, esto todavía le dará resultados instantáneos. :-) Y si lo ejecuta en el rango [0 - 1000000], obtiene la misma distribución exacta que la publicada por High-Performance Mark, por lo que estoy casi seguro de que es correcta.

FYI, la razón para la variable inner es que la función de cero principal ya es recursiva, por lo que solo se puede contar en la primera ejecución de countdigits .

Actualización 2: en caso de que el código sea difícil de leer, aquí hay una referencia de lo que significa cada línea de la declaración de retorno de los countdigits ( countdigits comentarios en línea pero hicieron que el código sea aún más difícil de leer):

1. Frecuencia de cualquier dígito hasta la potencia más alta de 10 (0-99, etc.)
2. Frecuencia de MSD por encima de cualquier múltiplo de la potencia más alta de 10 (100-399)
3. Frecuencia de cualquier dígito en el resto (400-445, R = 45)
4. Frecuencia adicional de MSD en el resto
5. Cuente ceros en la posición media para el rango restante (404, 405 ...)
6. Resta los ceros a la izquierda solo una vez (en el ciclo más externo)

Answer 4

Hice esta pregunta sobre el desbordamiento de matemáticas , y me dieron una paliza por hacer una pregunta tan simple. Uno de los usuarios se compadeció de mí y me dijo que si lo publicaba en The Art of Problem Solving , él lo respondería; Así que lo hice.

Aquí está la respuesta que publicó:
http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1741600#1741600

De manera vergonzosa, mi matemática es inadecuada para entender lo que publicó (el chico tiene 19 años ... eso es muy deprimente). Realmente necesito tomar algunas clases de matemáticas.

En el lado bueno, la ecuación es recursiva, por lo que debería ser una cuestión simple convertirla en una función recursiva con unas pocas líneas de código, por alguien que entienda las matemáticas.

Answer 5

Para sacar los dígitos de un número, solo tendríamos que hacer una costosa conversión de cadenas si no pudiéramos hacer un mod, los dígitos se pueden presionar más rápidamente de un número como este:

feed=number;
do
{ digit=feed%10;
  feed/=10; 
  //use digit... eg. digitTally[digit]++;
  }
while(feed>0)

ese bucle debe ser muy rápido y puede simplemente colocarse dentro de un bucle de los números de principio a fin para la forma más simple de contar los dígitos.

Para ir más rápido, para un mayor rango de números, estoy buscando un método optimizado para contar todos los dígitos de 0 a número * 10 ^ significado (de principio a fin me bazzogles)

Aquí hay una tabla que muestra el número de dígitos de algunos dígitos significativos. Estos incluyen 0, pero no el valor superior en sí mismo, eso fue un descuido, pero es quizás un poco más fácil ver patrones (sin los dígitos de los valores superiores ausentes). Estas cuentas no incluyen ceros al final,

  1 10 100 1000 10000 2 20 30 40 60 90 200 600 2000  6000

0 1 1  10  190  2890  1  2  3  4  6  9  30 110  490  1690
1 0 1  20  300  4000  1 12 13 14 16 19 140 220 1600  2800
2 0 1  20  300  4000  0  2 13 14 16 19  40 220  600  2800
3 0 1  20  300  4000  0  2  3 14 16 19  40 220  600  2800
4 0 1  20  300  4000  0  2  3  4 16 19  40 220  600  2800
5 0 1  20  300  4000  0  2  3  4 16 19  40 220  600  2800
6 0 1  20  300  4000  0  2  3  4  6 19  40 120  600  1800
7 0 1  20  300  4000  0  2  3  4  6 19  40 120  600  1800
8 0 1  20  300  4000  0  2  3  4  6 19  40 120  600  1800
9 0 1  20  300  4000  0  2  3  4  6  9  40 120  600  1800

editar: aclarando mis pensamientos originales:

de la tabla de fuerza bruta que muestra los recuentos de 0 (incluido) a poweroTen (notinc) es visible que un majordigit de tenpower:

increments tally[0 to 9] by md*tp*10^(tp-1)
increments tally[1 to md-1] by 10^tp
decrements tally[0] by (10^tp - 10) 
(to remove leading 0s if tp>leadingzeros)
can increment tally[moresignificantdigits] by self(md*10^tp) 
(to complete an effect)

si estos ajustes de recuento se aplicaron para cada dígito significativo, el conteo se debería modificar como si se contara de 0 al final-1

los ajustes se pueden invertir para eliminar el rango anterior (número de inicio)

Gracias a Aaronaught por su respuesta completa y probada.

Answer 6

Puede separar cada dígito ( mire aquí para ver un ejemplo ), cree un histograma con entradas de 0..9 (que contará cuántos dígitos aparecieron en un número) y multiplique por el número de ''números''.

Pero si no es lo que estás buscando, ¿puedes dar un mejor ejemplo?

Editado:

Ahora creo que tengo el problema. Creo que puedes contar esto (pseudo C):

int histogram[10];
memset(histogram, 0, sizeof(histogram));

for(i = startNumber; i <= endNumber; ++i)
{
    array = separateDigits(i);
    for(j = 0; k < array.length; ++j)
    {
        histogram[k]++;
    }
}

Los dígitos separados implementan la función en el enlace.

Cada posición del histograma tendrá la cantidad de cada dígito. Por ejemplo

histogram[0] == total of zeros
histogram[1] == total of ones

...

Saludos

Answer 7

Sé que esta pregunta tiene una respuesta aceptada, pero me encargaron escribir este código para una entrevista de trabajo y creo que se me ocurrió una solución alternativa que es rápida, no requiere bucles y puede usar o descartar ceros a la izquierda según sea necesario.

De hecho, es bastante simple pero no fácil de explicar.

Si enumera los primeros n números

     1
     2
     3

     .
     .
     .


     9
    10
    11

Es habitual comenzar a contar los dígitos requeridos desde el número de la sala de inicio hasta el número de la habitación final de izquierda a derecha, por lo que para los de arriba tenemos uno 1, uno 2, uno 3 ... uno 9, dos 1 uno cero , cuatro 1, etc. La mayoría de las soluciones que he visto utilizan este enfoque con alguna optimización para acelerarlo.

Lo que hice fue contar verticalmente en columnas, como en cientos, decenas y unidades. Usted conoce el número de habitación más alto, así que podemos calcular cuántos de cada dígito hay en la columna de centenas a través de una sola división, luego recurrir y calcular cuántos en la columna de decenas, etc. Luego, podemos restar los ceros a la izquierda si queremos.

Es más fácil de visualizar si usa Excel para escribir los números, pero usa una columna separada para cada dígito del número

     A    B    C
     -    -    -
     0    0    1  (assuming room numbers do not start at zero)
     0    0    2
     0    0    3
     .
     .
     .
     3    6    4
     3    6    5
     .
     .
     .

     6    6    9
     6    7    0
     6    7    1

     ^
     sum in columns not rows

Entonces, si el número de habitación más alto es 671, la columna de centenas tendrá 100 ceros verticales, seguidos por 100 unos y hasta 71 seises, ignorar 100 de los ceros si es necesario, ya que sabemos que todos estos son líderes.

Luego recurse a las decenas y realice la misma operación, sabemos que habrá 10 ceros seguidos por 10 unos, etc., repetidos seis veces, luego el tiempo final hasta 2 sietes. De nuevo, podemos ignorar los primeros 10 ceros, ya que sabemos que están liderando. Finalmente, por supuesto, haz las unidades, ignorando el primer cero según sea necesario.

Entonces no hay bucles, todo se calcula con división. Uso recursividad para viajar "arriba" de las columnas hasta que se alcanza el máximo (en este caso cientos) y luego retrocedo sumando como va.

Escribí esto en C # y puedo publicar código si alguien está interesado, no he hecho ninguna sincronización de referencia, pero es esencialmente instantánea para valores de hasta 10 ^ 18 habitaciones.

No se pudo encontrar este enfoque mencionado aquí ni en ningún otro lugar, por lo que pensé que podría ser útil para alguien.

Answer 8

Si "mejor" significa "más claro", entonces lo dudo. Si significa "más rápido", entonces sí, pero no usaría un algoritmo más rápido en lugar de uno más claro sin una necesidad imperiosa.

#!/usr/bin/ruby1.8

def digits_for_range(min, max, leading_zeros)
  bins = [0] * 10
  format = [
    ''%'',
    (''0'' if leading_zeros),
    max.to_s.size,
    ''d'',
  ].compact.join
  (min..max).each do |i|
    s = format % i
    for digit in s.scan(/./)
      bins[digit.to_i] +=1  unless digit == '' ''
    end
  end
  bins
end

p digits_for_range(1, 49, false) 
# => [4, 15, 15, 15, 15, 5, 5, 5, 5, 5]

p digits_for_range(1, 49, true)
# => [13, 15, 15, 15, 15, 5, 5, 5, 5, 5]

p digits_for_range(1, 10000, false)
# => [2893, 4001, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 4000]

Ruby 1.8, un lenguaje conocido como "perro lento", ejecuta el código anterior en 0.135 segundos. Eso incluye cargar el intérprete. No renuncies a un algoritmo obvio a menos que necesites más velocidad.

Answer 9

Si necesita velocidad sin procesar en muchas iteraciones, intente con una tabla de búsqueda:

1. Construya una matriz con 2 dimensiones: 10 x max-house-number

    int nDigits[10000][10] ;   // Don''t try this on the stack, kids!

2. Llene cada fila con el recuento de dígitos necesarios para llegar a ese número desde cero.
   Sugerencia: utilice la fila anterior como inicio:

    n=0..9999:
       if (n>0) nDigits[n] = nDigits[n-1]
       d=0..9:
           nDigits[n][d] += countOccurrencesOf(n,d)   // 

3. El número de dígitos "entre" dos números se convierte en simple resta.

For range=51 to 300, take the counts for 300 and subtract the counts for 50. 0''s = nDigits[300][0] - nDigits[50][0] 1''s = nDigits[300][1] - nDigits[50][1] 2''s = nDigits[300][2] - nDigits[50][2] 3''s = nDigits[300][3] - nDigits[50][3] etc.

Answer 10

Supongo que quiere una solución donde los números están en un rango, y tiene el número inicial y final. Imagínese comenzar con el número inicial y contar hasta llegar al número final; funcionaría, pero sería lento. Creo que el truco para un algoritmo rápido es darse cuenta de que para subir un dígito en el lugar de 10 ^ x y mantener todo lo demás igual, necesitas usar todos los dígitos antes de 10 ^ x veces más todos los dígitos 0 -9 10 ^ (x-1) veces. (Excepto que su recuento puede haber implicado un acarreo pasado el dígito x-ésimo; lo corrijo más abajo).

Aquí hay un ejemplo. Digamos que está contando de 523 a 1004.

• Primero, cuenta del 523 al 524. Esto usa los dígitos 5, 2 y 4 una vez cada uno.
• En segundo lugar, cuente de 524 a 604. El dígito más a la derecha hace 6 ciclos a través de todos los dígitos, por lo que necesita 6 copias de cada dígito. El segundo dígito pasa por los dígitos 2 a 0, 10 veces cada uno. El tercer dígito es 6 5 veces y 5 100-24 veces.
• En tercer lugar, cuente de 604 a 1004. El dígito más a la derecha tiene 40 ciclos, así que agregue 40 copias de cada dígito. El segundo desde el dígito derecho hace 4 ciclos, así que agrega 4 copias de cada dígito. El dígito más a la izquierda tiene 100 cada uno de 7, 8 y 9, más 5 de 0 y 100 - 5 de 6. El último dígito es 1 5 veces.

Para acelerar el último bit, mira la parte sobre los dos lugares más a la derecha. Utiliza cada dígito 10 + 1 veces. En general, 1 + 10 + ... + 10 ^ n = (10 ^ (n + 1) - 1) / 9, que podemos usar para acelerar el conteo aún más.

Mi algoritmo es contar desde el número de inicio hasta el número final (usando el recuento de base 10), pero use el hecho anterior para hacerlo rápidamente. Usted itera a través de los dígitos del número inicial de menor a mayor, y en cada lugar cuenta para que ese dígito sea el mismo que el número final. En cada punto, n es el número de recuentos que debe hacer antes de llevar a cabo un acarreo, ym el número que necesita hacer después.

Ahora supongamos que el pseudocódigo cuenta como un idioma. Aquí, entonces, es lo que haría:

convert start and end numbers to digit arrays start[] and end[] create an array counts[] with 10 elements which stores the number of copies of each digit that you need iterate through start number from right to left. at the i-th digit, let d be the number of digits you must count up to get from this digit to the i-th digit in the ending number. (i.e. subtract the equivalent digits mod 10) add d * (10^i - 1)/9 to each entry in count. let m be the numerical value of all the digits to the right of this digit, n be 10^i - m. for each digit e from the left of the starting number up to and including the i-th digit, add n to the count for that digit. for j in 1 to d increment the i-th digit by one, including doing any carries for each digit e from the left of the starting number up to and including the i-th digit, add 10^i to the count for that digit for each digit e from the left of the starting number up to and including the i-th digit, add m to the count for that digit. set the i-th digit of the starting number to be the i-th digit of the ending number.

Ah, y dado que el valor de i aumenta en uno cada vez, haga un seguimiento de sus 10 ^ i antiguos y simplemente multiplíquelo por 10 para obtener el nuevo, en lugar de exponenciar cada vez.

Answer 11

Tu enfoque está bien. No estoy seguro de por qué necesitarías algo más rápido que lo que has descrito.

O bien, esto le daría una solución instantánea: antes de que realmente lo necesite, calcule lo que necesitaría desde 1 hasta un número máximo. Puede almacenar los números necesarios en cada paso. Si tiene un rango como su segundo ejemplo, sería lo que se necesita para 1 a 300, menos lo que se necesita para 1 a 50.

Ahora tiene una tabla de búsqueda que se puede llamar a voluntad. Hacer hasta 10,000 solo tomaría unos MB y, ¿qué, unos minutos para computar, una vez?