Happy Number
Empieza con un entero positivo n y reemplázalo una y otra vez por la suma de los cuadrados de sus dígitos. Por ejemplo, 12 se convierte en 1² + 2² = 5. Si este proceso llega a 1, n es un número feliz; de lo contrario, da vueltas para siempre por números que nunca incluyen 1. Devuelve true si n es feliz y false si no lo es.
Función
- ninteger
- el entero positivo que se va a comprobar
- Devuelveboolean
- true si repetir la suma de los cuadrados de los dígitos llega a 1, false si entra en un bucle infinito
Restricciones
1 ≤ n ≤ 231-1
Ejemplos
- Entrada
- n = 7
- Salida
- true
- Explicación
- 7 se convierte en 49, después 4² + 9² = 97, después 130, después 10 y después 1. El proceso llega a
1, así que 7 es feliz.
- Entrada
- n = 2
- Salida
- false
- Explicación
- 2 se convierte en 4, 16, 37, 58, 89, 145, 42, 20 y después vuelve a 4. A partir de ahí, los mismos ocho números se repiten para siempre y nunca llegan a
1.
- Entrada
- n = 100
- Salida
- true
- Explicación
- 1² + 0² + 0² = 1, así que 100 llega a
1después de un paso.
+16 pruebas ocultas al enviar
Para ir más allá
¿Cómo contarías rápidamente los números felices del 1 al 10^6, reutilizando las respuestas para los números menores que 1000 en lugar de recorrer cada número inicial desde cero?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Prueba unos cuantos valores iniciales a mano. 7 llega a 1 en cinco pasos, mientras que 2 vuelve a 4 después de ocho pasos. ¿Qué te indica que un número vuelva?
Cada valor depende únicamente del anterior, así que, cuando se repite un número, todo el tramo posterior se repite para siempre. La pregunta pasa a ser: ¿la secuencia llega a 1 antes de llegar a un número que ya ha visto?
Mantén un conjunto de los números que has visitado y detente al llegar a 1 o al encontrar una repetición. Para usar memoria constante, haz avanzar dos recorridos desde
n, uno dando un paso por ronda y el otro dos; solo pueden encontrarse dentro de un ciclo.
Solución
El recorrido nunca puede llegar al infinito. Un número de 10 dígitos se asigna como máximo a 10 × 81 = 810, y un número menor que 1000 se asigna como máximo a 3 × 81 = 243, así que después de un paso el recorrido se mantiene entre menos de 1000 valores y debe llegar a 1 o repetir un número. Eso convierte el problema en una detección de ciclos: recuerda lo que has visto o ejecuta un recorrido lento y otro rápido y comprueba si se encuentran.
Recuerda todos los números que has visto
Intuición
Recorre la secuencia y guarda cada número en un conjunto hash. Antes de pasar de un número, comprueba si ya está en el conjunto. Para 2, el conjunto se llena con 2, 4, 16, 37, 58, 89, 145, 42 y 20, y el siguiente valor es 4, que ya está ahí: el recorrido ha cerrado un ciclo sin llegar a 1, así que 2 no es feliz. Llegar a 1 termina el recorrido con true.
Esto es correcto porque el siguiente número depende solo del actual. Cuando un número vuelve a aparecer, todo lo que viene después se repite exactamente, así que no puede aparecer ningún número nuevo, y nunca aparecerá 1.
El recorrido es corto. El primer paso lee los dígitos O(log n) de n, y cada valor posterior es menor que 1000, donde ningún recorrido visita más de 20 números distintos antes de llegar a 1 o repetir un número. El conjunto guarda esos números. El código C usa un arreglo de indicadores de 1000 entradas como conjunto y empieza a registrar después del primer paso, cuando todos los valores son menores que 1000.
Algoritmo
- Crea un conjunto hash vacío
seen. - Mientras
nno sea 1, devuelvefalsesinestá enseen. - De lo contrario, añade
naseeny reemplazanpor la suma de los cuadrados de sus dígitos. - Cuando el bucle termine,
nes 1: devuelvetrue.
def digitSquareSum(n):
total = 0
while n > 0:
digit = n % 10
total += digit * digit
n //= 10
return total
def isHappy(n):
seen = set()
while n != 1:
if n in seen:
return False # back at an earlier number: a loop without 1
seen.add(n)
n = digitSquareSum(n)
return Truecaminantes rápidos y lentos (detección de ciclos de Floyd)
Intuición
Piensa en cada número como un nodo con una flecha que apunta a la suma de los cuadrados de sus dígitos. Seguir las flechas desde n lleva a 1, cuya flecha apunta de vuelta a 1, o bien lleva a un bucle. Esa es la estructura de una lista enlazada que puede contener un ciclo, y el algoritmo de Floyd detecta un ciclo sin almacenar nada: slow avanza un paso por ronda y fast avanza dos.
Si el bucle no contiene 1, ambos caminantes terminan dando vueltas en él, y en cada ronda fast gana un paso a slow, así que la distancia se reduce en uno hasta que se encuentran en el mismo número. Para 2 se encuentran en 42 después de siete rondas. Si el recorrido llega a 1, fast llega primero y se queda allí, porque la suma para 1 es 1. Así que detente cuando fast sea 1 o los caminantes se encuentren, y responde si fast es 1.
Para 7, slow avanza por 7, 49, 97 mientras fast avanza por 49, 130, 1, y el bucle se detiene con fast en 1. El número de rondas es, como máximo, un múltiplo pequeño de la longitud del recorrido, así que el tiempo es igual que en la versión con conjunto, y la memoria ocupa dos enteros.
Algoritmo
- Escribe una función auxiliar que devuelva la suma de los cuadrados de los dígitos de un número.
- Asigna
slow = ny asigna afastel número que está un paso después den. - Mientras
fastno sea 1 yslowsea distinto defast, avanzaslowun paso yfastdos pasos. - Devuelve si
fastes 1.
def digitSquareSum(n):
total = 0
while n > 0:
digit = n % 10
total += digit * digit
n //= 10
return total
def isHappy(n):
slow = n
fast = digitSquareSum(n)
# fast moves two steps for every step of slow; they meet only inside a loop.
while fast != 1 and slow != fast:
slow = digitSquareSum(slow)
fast = digitSquareSum(digitSquareSum(fast))
return fast == 1
Errores comunes y casos límite
La aritmética de los dígitos es sencilla. La mayoría de los errores está en cuándo se detiene el bucle.
- Repetir el bucle hasta que el valor sea 1 sin ninguna otra condición de salida. Para 2, ese bucle nunca termina.
- Iniciar
slowyfastcon el mismo número y comprobarslow != fastantes del primer movimiento. El bucle nunca se ejecuta y 7 resulta ser un número infeliz. Iniciafastun paso por delante o mueve ambos antes de la primera comparación. - Devolver
slow == 1en la versión de Floyd.fastllega a 1 primero y el bucle se detiene enseguida, mientras queslowtodavía puede estar en 97. - Sumar los dígitos en vez de sus cuadrados, o elevar al cuadrado el número entero. Para 12, el siguiente valor es
1² + 2² = 5, no 3 ni 144. - Declarar que
nes infeliz siempre que los cursores se encuentren. 1 se transforma en sí mismo, así que los cursores también se encuentran en 1; comprueba dónde se encontraron o detente en cuantofastsea 1.
Preguntas frecuentes4
¿Por qué el proceso siempre llega a 1 o a un bucle?
Un número con d dígitos se transforma en un valor de como máximo 81 × d, así que los números grandes se reducen rápidamente: cualquier valor inicial de hasta 2^31-1 baja de 1000 después de un paso, y un número inferior a 1000 se transforma en un valor de como máximo 243. La secuencia queda atrapada entre menos de 1000 valores, así que necesariamente vuelve a uno de ellos y, a partir de entonces, entra en un ciclo. 1 es el único número que se transforma en sí mismo.
¿Cuál es la complejidad temporal de Happy Number?
El primer paso lee los dígitos de n en O(log n). Todos los valores posteriores son menores que 1000, y el recorrido se repite en 20 números como máximo, así que el tiempo total es O(log n). La versión con conjunto hash almacena los números visitados; la versión de Floyd usa espacio O(1).
¿Por qué todos los números infelices terminan en 4?
Al comprobar todos los números menores que 1000, se observa exactamente un ciclo que no incluye el 1: 4, 16, 37, 58, 89, 145, 42, 20 y vuelta al 4. Como cada punto de partida desciende por debajo de 1000, todos los números no felices caen en él. Una solución puede detenerse en cuanto llega al 4, pero eso se basa en un hecho que tendrías que justificar en una entrevista; el conjunto y el método de Floyd no requieren ese conocimiento.
¿Qué relación tiene el número feliz con el ciclo de una lista enlazada?
Ambos preguntan si, al seguir una flecha desde cada elemento, se vuelve alguna vez a un elemento ya visitado. En Happy Number, la flecha es la suma de los cuadrados de los dígitos; en una lista enlazada, es el puntero al siguiente elemento. Por eso los recorridos rápido y lento de Floyd resuelven ambos problemas con memoria constante.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def isHappy(n):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
n = 7
Esperado
true