Count Digits

Q: ¿Por qué 0 tiene un dígito?

Cero se escribe con el carácter único 0 , así que su forma decimal tiene un dígito. El código que cuenta las divisiones mientras el número es mayor que 0 nunca se ejecuta para 0 y devuelve 0. Si se inicia el contador en 1 y se divide mientras el número es al menos 10, se maneja sin ningún caso especial.

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 redondear en la dirección equivocada: log10(10^15-1) da exactamente 15 en precisión doble. La división entera da la respuesta exacta siempre.

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

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

PrincipianteMatemáticas y simulación

+10

Escribe una función que reciba un entero no negativo n y devuelva cuántos dígitos tiene al escribirlo 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: la cantidad de dígitos decimales en 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 solo dígito. Un bucle que cuenta mientras el número sea mayor que 0 nunca se ejecuta aquí y devolvería 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.

+16 pruebas ocultas al enviar

Para ir más allá

¿Puedes contar los dígitos sin 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

La cantidad de dígitos es el número de veces que puedes dividir entre 10 antes de que quede un dígito, más ese dígito. La idea cabe en una línea; el trabajo está en los casos límite. 0 tiene un dígito, la cantidad cambia entre 9 y 10, y una fórmula basada en logaritmos falla con 0 y, en coma flotante, un poco por debajo de las potencias grandes de diez.

Escribe el número como texto y cuenta los caracteres

Intuición

Tu lenguaje ya sabe cómo escribir n en decimal. Pídele esa cadena y cuenta los caracteres: 4096 se convierte en "4096", cuatro caracteres. 0 se convierte en "0", un carácter, así que el cero no necesita ningún caso especial.

La conversión divide entre 10 dentro de la biblioteca, una vez por dígito, así que el trabajo es O(log n). La cadena contiene un carácter por dígito, lo que supone O(log n) de memoria adicional, como máximo 10 caracteres en este caso.

El formato debe ser decimal simple. En R, as.character(1e5) devuelve "1e+05", cinco caracteres para un número de seis dígitos, así que aplica el formato con sprintf("%.0f", n). En Lua 5.3 y versiones posteriores, tostring(4096.0) conserva el .0, mientras que string.format("%d", n) escribe el entero en todas las versiones.

Algoritmo

Convierte n en su cadena decimal con una función que nunca cambie 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

La división entera entre 10 elimina el último dígito: 4096 / 10 es 409. Cada división quita un dígito, así que la respuesta es el número de divisiones necesarias para llegar a un solo dígito, más uno por ese último dígito. 4096 necesita tres divisiones (409, 40, 4), así que tiene 4 dígitos.

Empieza el conteo en 1 y divide mientras n ≥ 10. Empezar en 1 indica que todo número tiene al menos un dígito, que es exactamente la regla para 0. La versión que la gente suele escribir primero, contando desde 0 mientras n > 0, devuelve 0 para n = 0 y necesita una comprobación aparte.

El bucle se ejecuta una vez por cada dígito después del primero, como máximo 9 veces para 2147483647, así que tarda O(log n). Mantiene un contador y modifica su propia copia de n, lo que requiere O(1) de espacio adicional.

Algoritmo

Establece count = 1, para el dígito que siempre está ahí.
Mientras n ≥ 10, divide n entre 10 mediante división entera y suma 1 a count.
Cuando quede un dígito, return 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

Todos los errores de este problema se encuentran en un límite.

Contar desde 0 mientras n > 0. Es correcto para todos los números positivos y devuelve 0 para n = 0.
Usar floor(log10(n)) + 1. Falla con 0, cuyo logaritmo es menos infinito, y con valores grandes ligeramente inferiores a una potencia de diez: en doble precisión, log10(10^15-1) se redondea exactamente a 15, por lo que la fórmula indica 16 dígitos en lugar de 15.
División real en un bucle que se ejecuta mientras n > 0. En JavaScript, Lua, PHP y R, / conserva la parte fraccionaria, así que 4096 se reduce hacia 0 durante 328 pasos antes de llegar a él. Usa Math.floor, math.floor, intdiv o %/%.
Notación científica en la versión con cadenas: R escribe 100000 como "1e+05".
Contar el signo menos como un dígito. La entrada aquí nunca es negativa, pero String(-42) tiene tres caracteres, así que una versión para números negativos toma primero el valor absoluto.

Preguntas frecuentes4

¿Cómo cuentas los dígitos de un número sin convertirlo en una cadena?

Divídelo entre 10 usando división entera hasta que quede un dígito, contando las divisiones, y suma 1 para el último dígito. 4096 se convierte en 409, 40, 4: tres divisiones, así que son 4 dígitos. El bucle usa espacio adicional O(1).

¿Por qué 0 tiene un dígito?

Cero se escribe con el carácter único 0, así que su forma decimal tiene un dígito. El código que cuenta las divisiones mientras el número es mayor que 0 nunca se ejecuta para 0 y devuelve 0. Si se inicia el contador en 1 y se divide mientras el número es al menos 10, se maneja sin ningún caso especial.

¿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 redondear en la dirección equivocada: log10(10^15-1) da exactamente 15 en precisión doble. La división entera da la respuesta exacta siempre.

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

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

Python

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

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

n = 4096

Esperado