Armstrong Number

Q: ¿Cuál es la complejidad temporal de comprobar si un número es de Armstrong?

n tiene aproximadamente log n dígitos, como máximo 10 en este caso. Extraer los dígitos y consultar cada potencia en una tabla de diez elementos requiere un tiempo de O(log n) y un espacio de O(1) . Volver a calcular d^k con un bucle para cada dígito hace que sea O(log² n) , sigue siendo rápido para este tamaño.

PrincipianteMatemáticas y simulación

+10

Un entero positivo es un número de Armstrong cuando es igual a la suma de sus propios dígitos, cada uno elevado a la potencia del número de dígitos que tiene. 153 tiene tres dígitos y 1^3 + 5^3 + 3^3 = 153, así que es uno. Escribe una función que reciba n y devuelva true si es un número de Armstrong y false en caso contrario.

Función

isArmstrong(n: integer) → boolean

ninteger: el entero positivo que se va a comprobar
Devuelveboolean: verdadero cuando n es igual a la suma de sus dígitos, cada uno elevado al número de dígitos

Restricciones

1 ≤ n ≤ 10⁹

Ejemplos

Entrada: n = 153
Salida: true
Explicación: 153 tiene 3 dígitos, así que se eleva al cubo cada dígito: 1 + 125 + 27 = 153. La suma da como resultado el mismo número, así que la respuesta es true.

Entrada: n = 10
Salida: false
Explicación: 10 tiene 2 dígitos, así que se eleva al cuadrado cada dígito: 1 + 0 = 1, que no es 10. La respuesta es false.

Entrada: n = 9474
Salida: true
Explicación: Con 4 dígitos, la potencia es 4: 6561 + 256 + 2401 + 256 = 9474, el número en sí, así que la respuesta es true.

+31 pruebas ocultas al enviar

Para ir más allá

Solo hay 31 números de Armstrong entre 1 y 10^9. ¿Puedes enumerarlos todos sin probar mil millones de números uno por uno?

Pistas

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

0 de 3 abiertas

Solución

La definición es el algoritmo: encuentra cuántos dígitos tiene n, eleva cada dígito a esa potencia, suma los resultados y compáralos con n. Las trampas están en los números. El exponente es la cantidad de dígitos de este n en particular, no un 3 fijo, y la suma puede superar un entero de 32 bits: para 999999999 es 9 × 9^9 = 3486784401.

Lee los dígitos de la cadena

Intuición

La cadena decimal de n te proporciona las dos cosas que necesitas. Su longitud es el exponente k, y sus caracteres son los dígitos. Para 9474, la cadena tiene 4 caracteres, así que sumas 9^4 + 4^4 + 7^4 + 4^4.

Convierte cada carácter de nuevo en su dígito, elévalo a la potencia k y súmalo a un total acumulado. n es un número de Armstrong exactamente cuando el total final es igual a n.

Mantén el total en un entero de 64 bits. n cabe en 32 bits, pero la suma no necesariamente: 999999999 da 3486784401, que supera el límite de 32 bits de 2147483647. Calcular una potencia con un bucle de k multiplicaciones cuesta k pasos por dígito, así que la comprobación es O(k²), con k aproximadamente igual a log n. En este caso, son como máximo 100 multiplicaciones, y la cadena ocupa k caracteres de memoria.

Algoritmo

Convierte n en su representación decimal como cadena y deja que k sea su longitud.
Establece un total de 64 bits en 0.
Para cada carácter, conviértelo en su dígito d y suma d^k a total, multiplicando números enteros en lugar de llamar a una función de potencia de coma flotante.
Devuelve si total es igual a n.

def isArmstrong(n):
    digits = str(n)
    k = len(digits)
    total = 0
    for ch in digits:
        total += int(ch) ** k
    return total == n

Separa los dígitos y busca sus potencias

Intuición

La aritmética por sí sola hace lo mismo sin una cadena. m % 10 es el último dígito de m y la división entera entre 10 lo elimina, así que un bucle que divide entre 10 hasta que no queda nada cuenta los dígitos. 9474 se convierte en 947, 94, 9, 0: cuatro pasos, así que k = 4.

Solo existen diez dígitos, así que crea una tabla powers[d] = d^k para d desde 0 hasta 9 antes de sumar nada. Cada dígito requiere entonces una consulta a la tabla en lugar de k multiplicaciones. La comprobación se reduce a un tiempo de O(log n), y la tabla tiene un tamaño fijo de diez, lo que supone un espacio de O(1).

El segundo bucle vuelve a extraer los dígitos y suma powers[m % 10] al total. Todos los términos son cero o positivos, así que el total nunca disminuye, y una vez que supera n, la respuesta es false. Para 999999999, eso ocurre después de tres dígitos, en 3 × 387420489 = 1162261467. La tabla sigue necesitando 64 bits, porque n = 10^9 tiene diez dígitos y 9^10 = 3486784401.

Algoritmo

Cuenta los dígitos de n dividiendo una copia entre 10 hasta que llegue a 0; llama k al recuento.
Llena powers[d] = d^k para cada dígito d del 0 al 9, usando enteros de 64 bits.
Vuelve a dividir entre 10 una copia nueva de n, sumando powers[m % 10] a total en cada paso.
Si total supera n, devuelve false de inmediato.
Después del último dígito, devuelve si total es igual a n.

def isArmstrong(n):
    # Count the digits: k is the exponent.
    k = 0
    m = n
    while m > 0:
        k += 1
        m //= 10
    # powers[d] = d^k for the ten possible digits.
    powers = [d ** k for d in range(10)]
    total = 0
    m = n
    while m > 0:
        total += powers[m % 10]
        if total > n:
            return False  # the total only grows
        m //= 10
    return total == n

Errores comunes y casos límite

La fórmula es corta, así que los errores vienen de los números que la rodean.

Un exponente fijo de 3. Acepta 153 y 370, pero rechaza 9474, y rechaza todos los números de un solo dígito mayores que 1, ya que 7^3 = 343.
Una suma de 32 bits. 999999999 da como suma 3486784401 y la entrada de la tabla 9^10 es el mismo número. En C, ese desbordamiento tiene un comportamiento indefinido; Java y C# lo convierten en un número negativo, y una compilación de depuración de Rust provoca un pánico. Usa long, long long o i64.
Potencias de punto flotante. pow en C y Math.pow en Java devuelven un double. Algunos entornos de ejecución de C han devuelto un valor ligeramente inferior a un número entero, como 24.999... para 5^2, que una conversión de tipo trunca a 24. En su lugar, multiplica números enteros en un bucle.
Comparar con el valor incorrecto. Los bucles de dígitos dividen n hasta llegar a 0, así que trabaja con una copia y compara el total con el valor original.
Notación científica. En R, as.character(1e9) es "1e+09", cinco caracteres, por lo que una solución basada en cadenas en R da formato con sprintf("%.0f", n).

Preguntas frecuentes4

¿Qué es un número de Armstrong?

Un número de Armstrong, también llamado número narcisista, es igual a la suma de sus propios dígitos, cada uno elevado a la potencia del número de dígitos. 153 es uno porque 1^3 + 5^3 + 3^3 = 153, y 9474 es uno porque 9^4 + 4^4 + 7^4 + 4^4 = 9474. Todos los números de un dígito cumplen esta condición, ya que d^1 = d.

¿Cuántos números de Armstrong hay?

En base 10 hay exactamente 88 números positivos de este tipo, y el mayor tiene 39 dígitos. La lista es finita porque un número de k dígitos es al menos 10^(k-1), mientras que la suma de las potencias de sus dígitos es como máximo k × 9^k, y a partir de 61 dígitos la suma nunca puede alcanzarlo. Entre 1 y 10^9 hay 31.

¿Por qué la comprobación del número de Armstrong necesita un entero de 64 bits?

La entrada cabe en 32 bits, pero la suma de los dígitos elevados a una potencia puede ser varias veces mayor que el número. 999999999 da 9 × 9^9 = 3486784401, que supera 2^31-1 = 2147483647. Un total de 32 bits se desborda en ese caso, así que guarda el total y las potencias en un tipo de 64 bits.

¿Cuál es la complejidad temporal de comprobar si un número es de Armstrong?

n tiene aproximadamente log n dígitos, como máximo 10 en este caso. Extraer los dígitos y consultar cada potencia en una tabla de diez elementos requiere un tiempo de O(log n) y un espacio de O(1). Volver a calcular d^k con un bucle para cada dígito hace que sea O(log² n), sigue siendo rápido para este tamaño.

Python

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

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

n = 153

Esperado

true