¿Cuántas veces aparecerá cada dígito del 0 al 9 cuando todos los números del 1 al N estén escritos en notación decimal?

Podemos resolver esto mirando los dígitos en cada posición por separado. Por ejemplo, sea N = 1048365. Contaremos cuántas veces aparece el dígito d en la posición 8 actual. Escriba N como LcR, con L = 104, c = 8 y R = 365. Consideraremos cuatro casos.

Caso 1: d = 0
En este caso, cada número que tenga 0 en la posición actual de 8 debe tener la forma M0S. Como los números se escriben sin ceros a la izquierda, M debe ser al menos 1. Y dado que L = 104, M también puede ser 104 como máximo. Para cada valor de M, S puede ser cualquier cadena numérica en [000 … 999]. Por lo tanto, el número total de veces que 0 aparece en la posición actual de 8 es 104 × 1000 = 104000.

Caso 2: 1≤d≤7
Se aplican las mismas condiciones que antes, excepto por el hecho de que M = 0 también proporciona soluciones válidas. Por lo tanto, el número de veces que d aparece en la posición actual de 8 es 105 × 1000 = 1050000.

Caso 3: d = 8
En este caso, tener M de [0 … 103] permite los 1000 valores de S como antes. Pero tener M = 104 nos permite solo S de [0 … 365] ya que tomar una S más alta nos dará un número mayor que N. Por lo tanto, el número total de veces que aparece 8 es 104 × 1000 + 366 = 104366.

Caso 4: d> 8
En este caso, podemos tener M solo en el rango [0 … 103]. Para cada valor de M, todos los 1000 valores de S están permitidos y el número total de veces que aparece d es 104 × 1000 = 104000.

Repita el procedimiento para cada posición en N y cada dígito d. Los recuentos de todos los dígitos pueden calcularse en O (10 log N).

Algoritmo de estructura de datos Preguntas de entrevistaAlgoritmosentrevistas de programaciónProgramación informática

¿Cuál es el propósito de la pregunta 'cuál fue su error más difícil' en las entrevistas para puestos de ingeniería de software?

¿Por qué hay una gran diferencia entre las preguntas de algoritmos en una entrevista técnica y el desarrollo de software real?

¿Por qué las entrevistas tecnológicas se centran en problemas o algoritmos complicados de la estructura de datos cuando la mayoría de las empresas no requieren esto en el trabajo diario?

Cómo prepararse para las preguntas de la entrevista técnica de TCS

Dado un conjunto de cadenas, ¿cómo puedo encontrar un pequeño conjunto de subcadenas de modo que el conjunto de cadenas se pueda dividir en función de las subcadenas coincidentes con una distribución razonablemente uniforme?

¿Cómo se puede dividir una secuencia de enteros ‘n’ en particiones contiguas y no vacías ‘m’ de manera eficiente de modo que la suma de los máximos de todas las particiones ‘m’ sea mínima (m <n)?

El método más simple sería mirar todos los números hasta [math] N [/ math] como una cadena e iterar a través de la matriz para contar. Se planteó un problema similar en la ronda de calificación en línea de ICPC 2013.

Código de muestra:

  // Función para convertir enteros a cadena

 string intToString (int n) {
     stringstream ss;
     ss << n;
    
     return ss.str ();
 }

 int main ()
 {
 cuerda
 para (int i = 1; i <= N; i ++)
      s + = intToString (i);

 string digit = "0123456789";

 vector  cuenta;

 para (int i = 0; i

Sunil Kumar

#include
#include
#include

usando el espacio de nombres estándar;

string intToString (int num) {

stringstream ss;
ss << num;

return (ss.str ());
}

int main () {

int num;
int dig [10]; // num de 0-9

cout << "Ingrese la cadena" << endl;
cin >> num;
cout << "Cadena de entrada =" << num << endl;

cadena str = intToString (num);

para (int i = 0; i <10; i ++) {
dig [i] = 0;
}
for (int i = 0; i cout << str [i] << endl;
dig [std :: stoi (str [i])] ++;
}

para (int i = 0; i <10; i ++) {
cout << "Digit" << i << "aparece" << dig [i] << "times" << endl;
}