Es una pregunta de la entrevista.Dado un número n, averigüe cuántos números tienen el dígito 2 en el rango 0 ... n
Dado un número n, averiguar la cantidad de números tiene 2 dígitos en el rango de 0 ... n
Por ejemplo,
entrada = 13 salida = 2 (2 y 12)
He dado la solución O (n^2) habitual pero hay un mejor enfoque.
¿hay alguna fórmula 'truco' que me ayudará a obtener la respuesta de inmediato
Contar los números que hacer no tienen el dígito 2. Entre los números menores de 10 k , hay exactamente 9 k de ellos. A continuación, se mantiene para el tratamiento de los números del 10 k-n, donde
10^k <= n < 10^(k+1)
que se puede hacer mediante el tratamiento de los primeros dígitos de forma individual (los casos 2 y otros tienen que ser diferenciadas), y luego el primer 2 dígitos, etc.
Por ejemplo, para n = 2345, encontramos que hay 9^3 = 729 números sin el dígito 2 por debajo de 1000. Hay de nuevo 729 números en el rango de 1000 a 1999. Luego en el rango de 2000 a 2345, hay no son ninguno, para un total de 1458, por lo tanto, los números que contienen el dígito 2 son
2345 - 1458 = 887
¿Podría explicar cómo obtuvo 9^k números, no soy muy bueno con la combinatoria. – nikhil
Si escribe números con ceros a la izquierda, los números 0 a '10^k - 1' son precisamente los números que puede escribir con exactamente' k' dígitos. Para cada uno de los dígitos, hay 9 ('== 10 - 1') opciones posibles (' 0,1,3,4,5,6,7,8,9'). Las elecciones son independientes, por lo que el número total de opciones es el producto de la cantidad de opciones para cada dígito, '9 * 9 * ... * 9 = 9^k'. Si busca los números que no contienen un dígito 2 ni un dígito 5, sería '8^k' (8 = 10 - 2). El mismo principio se aplica a las representaciones de números en otras bases. Sin embargo, dado que los números en realidad no tienen ceros a la izquierda, cont ... –
..., que prohíbe el dígito 0 es ligeramente diferente. Entonces no puede agregar ceros a la izquierda para obtener todos los números a la misma longitud, y la cuenta de números debajo de '10^k' que no tiene un dígito 0 es '9^1 + 9^2 + 9^3 + ... + 9^k = 9 * (9^k - 1)/8'. Si prohibes 0 y 'd' otros dígitos, dejando' e = 9-d' dígitos elegibles, obtienes 'e^1 + e^2 + ... + e^k = e * (e^k - 1)/(e-1) '. (Reemplace 9 por 'base-1' para bases que no sean 10.) –
Dado el número con los dígitos ABCDEF puede contar el número de 'de 2 en los rangos [0,F], [0,E9], [0,D99], [0,C999], [0,B9999] y [0,A99999] y añadirlos.
Luego, para el rango [0, X9999...999], el número superior T = X9999...999 se puede escribir como (X+1) * 10<sup>nines</sup> -1.
El número de 'de 2 en ese rango es:
((X >= 2 ? 1/(X + 1)) : 0) + nines/10) * (T + 1);
Eso es: si X >= 2, la fracción de números que tienen un '2' en los nueves de posición + 1 es 1/(X+1), en total existen (T+1)/(X+1) '2 en esa posición. Si es X < 2, entonces ningún número en [0..T] tiene un '2' en esa posición.
Para las otras posiciones de dígito, es fácil ver que en cada posición de dígito, 1/10 de los números tienen un '2', por lo que hay (T+1)/10 '2 de en la posición 0, (T+1)/10' 2'S en posición 1, etc. En total, (T+1) * nines/10.
La complejidad de esta solución es O (logN).
esto es cómo iba a ir sobre la codificación de mi primer proyecto (código Python)
def count2(n) :
return [p for p in range(n+1) if '2' in str(p)]
y que le devolverá una lista con el número que contiene.
En términos de rendimiento no es tan malo, para n = 10,000,000 una iteración promedio tarda aproximadamente 5,5 segundos
argumento 'dígito' es la que queremos contar y arg 'número' es, hasta donde quiero contar Por ejemplo: si queremos contar las ocurrencias de '1', de 0 a 12, llame a la función con digit = 1, y number = 12, y devolverá el número de ocurrencias de '1'.
int countOccurrences(int digit, int number)
{
int counter = 0;
for(int i=1; i<number; i++)
{
int j = i;
while(j > 0)
{
if(j%10 == digit)
counter++;
j /= 10;
}
}
return counter;
}
Explíquelo con alguna explicación. – Sankarann
countOccurrences (1,20) = 3; // incorrecto – SMUsamaShah
¿Has intentado ejecutar este método? Devuelve 12, en countOccurrences (1,20), no 3. – undeadlock
O (n²)? Si quiere decir, generar los números y verificar los dígitos, eso es O (n lg n), ya que cada número n está representado por O (lg n) dígitos. –
Es una pregunta de permuttación. –