Count Digits

Q: ¿Cuál es la complejidad temporal de contar dígitos?

Un número n tiene floor(log10(n)) + 1 dígitos, y el bucle realiza una división por dígito, por lo que se ejecuta en tiempo O(log n) y espacio O(1) . Para un entero de 32 bits, son como máximo 10 pasos.

Q: ¿Puedes usar log10 para contar los dígitos de un número?

Para un n positivo, el conteo es floor(log10(n)) + 1 , pero el logaritmo se calcula en coma flotante. No está definido para 0 y, cerca de una potencia de diez, puede redondearse en la dirección equivocada: log10(10^15-1) da exactamente 15 en precisión doble. La división entera siempre es exacta.

PrincipianteMatemáticas y simulación

+10

Dado un entero no negativo n, devuelve cuántos dígitos tiene al escribirse en base 10 sin ceros iniciales. El cero se escribe como un único 0, así que tiene un dígito.

Función

countDigits(n: integer) → integer

ninteger: el entero no negativo que se va a medir
Devuelveinteger: el número de dígitos decimales de n

Restricciones

0 ≤ n ≤ 2³¹-1

Ejemplos

Entrada: n = 4096
Salida: 4
Explicación: La división entera entre 10 convierte 4096 en 409, 40 y 4: se eliminan tres dígitos y queda uno, así que la respuesta es 4.

Entrada: n = 0
Salida: 1
Explicación: 0 se escribe con un dígito. Un bucle que cuenta mientras el número sea mayor que 0 nunca se ejecuta aquí y devuelve 0 en lugar de 1.

Entrada: n = 100
Salida: 3
Explicación: Los ceros también son dígitos: 100 se escribe 1, 0, 0, así que la respuesta es 3.

Para ir más allá

¿Puedes contar los dígitos sin usar un bucle que se ejecute una vez por cada dígito, por ejemplo, mediante una búsqueda binaria entre las potencias de diez?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Cada división entera entre 10 elimina un dígito. Cuenta las divisiones hasta que quede un dígito y luego suma uno por ese dígito. Los errores aparecen en los casos límite: 0 tiene un dígito, y una fórmula logarítmica falla con 0 y un poco por debajo de las potencias de diez grandes.

Escribe el número como texto y cuenta los caracteres

Intuición

Tu lenguaje ya escribe n en decimal. Pide esa cadena y cuenta sus caracteres: 4096 se convierte en "4096", cuatro caracteres, y 0 se convierte en "0", así que el cero no necesita ningún caso especial.

La conversión realiza una división por dígito, así que tanto el tiempo como la memoria adicional son O(log n), como máximo 10 caracteres aquí.

Algoritmo

Convierte n en su cadena decimal con una función que nunca cambia a notación científica.
Cuenta los caracteres de la cadena.
Devuelve ese recuento. Para 0, la cadena es "0", así que la respuesta es 1, sin ninguna comprobación adicional.

def countDigits(n):
    return len(str(n))

Divide entre 10 hasta que quede un dígito

Intuición

Empieza la cuenta en 1 y divide entre 10 mientras n ≥ 10, sumando 1 por cada división. Empezar en 1 indica que todo número tiene al menos un dígito, que es exactamente la regla para 0, así que no hace falta ninguna comprobación aparte.

El bucle se ejecuta como máximo 9 veces, para 2147483647: tiempo O(log n). Mantiene un contador y modifica su propia copia de n, así que el espacio adicional es O(1).

Algoritmo

Establece count = 1, para el dígito que siempre está ahí.
Mientras n ≥ 10, divide n entre 10 usando división entera y suma 1 a count.
Cuando quede un dígito, devuelve count.

def countDigits(n):
    count = 1  # every number, 0 included, has at least one digit
    while n >= 10:
        n //= 10
        count += 1
    return count

Errores comunes y casos límite

Contar desde 0 mientras n > 0. Devuelve 0 para n = 0.
Usar floor(log10(n)) + 1. Falla con 0, donde el logaritmo es menos infinito, y con 10^15-1, donde la precisión doble redondea el logaritmo exactamente a 15 y la fórmula indica que hay 16 dígitos.
La división real en JavaScript, Lua, PHP o R, donde / conserva la fracción. Un bucle mientras n > 0 se ejecuta después 328 veces para 4096. Usa Math.floor, math.floor, intdiv o %/%.
Notación científica en la versión con cadenas. R escribe as.character(1e5) como "1e+05"; usa sprintf("%.0f", n). En Lua 5.3 y versiones posteriores, tostring(4096.0) conserva el .0; usa string.format("%d", n).

Preguntas frecuentes3

¿Cuál es la complejidad temporal de contar dígitos?

Un número n tiene floor(log10(n)) + 1 dígitos, y el bucle realiza una división por dígito, por lo que se ejecuta en tiempo O(log n) y espacio O(1). Para un entero de 32 bits, son como máximo 10 pasos.

¿Puedes usar log10 para contar los dígitos de un número?

Para un n positivo, el conteo es floor(log10(n)) + 1, pero el logaritmo se calcula en coma flotante. No está definido para 0 y, cerca de una potencia de diez, puede redondearse en la dirección equivocada: log10(10^15-1) da exactamente 15 en precisión doble. La división entera siempre es exacta.

¿Cómo cuentas los dígitos de un número negativo?

Primero toma el valor absoluto y después cuenta como de costumbre. String(-42) tiene tres caracteres porque el signo menos no es un dígito. Para el entero de 32 bits más pequeño, toma el valor absoluto en un tipo de 64 bits, ya que no cabe en 32 bits.

def countDigits(n):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

n = 4096

Salida Esperada