En Codeforces Round # 308 (Div. 2), ¿cómo descubrieron todos la cantidad de dígitos de un número usando un algoritmo eficiente de toma de tiempo? ¿Alguien puede explicarlo?

Es un simple problema de implementación. En primer lugar, multiplique n con el número de dígitos de n.
Entonces, por ejemplo, si n es 113, multiplicamos 113 con 3 (número de dígitos en el número 113) e inicializamos esto como nuestra respuesta.
Luego necesitamos restar los dígitos adicionales que hemos contado. Para 1-9, hemos contado 2 dígitos adicionales para cada uno de ellos, para 10-99 hemos contado 1 dígito adicional para cada uno de ellos. Para 100-113 lo hemos contado correctamente. Entonces tenemos que restar estos dígitos adicionales de nuestra respuesta inicial. Podemos hacer esto con un bucle for simple. La implementación de muestra se da a continuación:

ans = n * tamaño de (n)
para (int x = 10; x <= n; x * = 10)
ans – = (x-1);
imprimir (ans)

En cada iteración, ninguno de los dígitos adicionales de cada número en el rango se reduce en 1
Entonces, para 113 la respuesta se convierte en 113 * 3 – (9) – (99) = 231.
Espero que esto ayude.

¿Cuál es la complejidad temporal de una función que calcula la altura de un árbol binario de forma recursiva? ¿Es O (N) u O (NlogN)?

¿Cómo se debe comenzar a aprender Algoritmos?

Soy nuevo en Quora y no entiendo si las preguntas de coeficiente intelectual son una tendencia constante o si estoy atrapado en alguna forma de algoritmo infernal. Si es así, ¿cómo escapo?

¿Cuáles son los algoritmos que se pueden usar en aplicaciones web del mundo real además de ordenar o buscar?

¿Cuáles son algunos algoritmos que todo programador debe aprender / saber?

¿Hay alguna forma algorítmica de distinguir palabras multisilábicas de palabras de una sola sílaba en inglés?

Supongamos que la respuesta es X. Ahora X = 1 * a1 + 2 * a2 + 3 * a3 ……,
donde a1 = número de números de 1 dígito que escribe
a2 = número de 2 dígitos que escribe y así sucesivamente.
Veamos si podemos resolver estos a1, a2 …
Primero observe:
Número de números de 1 dígito = 9
Número de números de 2 dígitos = 90
Número de números de 3 dígitos = 900 y la tendencia continúa.

Si la entrada es N, ¿cómo encontramos el número de números de 1 dígito que escribe? Simple, divide N por 10, si el cociente es mayor que 0 escribe los 9 números. Si el cociente es 0, simplemente comenzamos a contar el número de números de un solo dígito desde 1 hasta N.
Ahora espere, esta misma estrategia también se puede usar para contar el número de números de 2 dígitos, dividimos por 100 y si el cociente no es cero, escribe 90 números, de lo contrario comenzamos a contar desde 10.

Ahora ves, seguimos dividiendo por potencias de 10 y en el momento en que llegamos a cero, comenzamos a contar desde la última potencia de 10 que resultó en un cociente distinto de cero. Este conteo es el último coeficiente que estamos buscando en nuestra fórmula anterior. Ahora sustituya estos coeficientes y obtenga la respuesta.

Aquí está el código
int base = 9;
int i, rdx;
int num;
largo largo ans = 0;
cin >> num;
para (i = 1; i <= 10; i ++)
{
rdx = num / exp (10, i);
si (rdx> 0)
{ans + = base * i;
base = base * 10;
}
más
{para (int j = exp (10, i-1); j <= num; j ++)
ans + = i;
descanso;
}
}
cout << ans << endl;

Vibhor Kanojia

Tomemos un ejemplo y consideremos que no. 117)
Hay 18 (100-117) números de 3 dígitos, 90 (10-99) números de 2 dígitos y 9 (1-9) número de 1 dígito.
Creé dos matrices,

llint poderes [] = {0,10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
llint resto [] = {0,9,90,900,9000,90000,900000,9000000,90000000,900000000};

1) Entonces, primero calcule el número de dígitos (llamémoslo num_digits) en ese número usando log (n) , 3 en este caso.
2) Ahora usando la matriz de ‘ potencias ‘, encuentre los bits en exceso, es decir, 117 -100 = 17 en este caso.
3) Por lo tanto, debe usar 3 * (17 + 1) dígitos para los números 100 – 117 .
4) Después de esto, solo tiene que ejecutar un bucle de num_digits a 0 y agregar 90 * 2 y 9 * 1 utilizando la matriz ‘ resto’ .