Problema
Partiendo de cualquier n positivo, la regla de Collatz dice que el siguiente término es n / 2 si n es par y 3n + 1 si n es impar; la cadena termina al llegar a 1. La cadena de 6 es 6, 3, 10, 5, 16, 8, 4, 2, 1: nueve términos. De todos los números iniciales del 1 a limit, encuentra el que tiene más términos.
Implementa longest_collatz_chain(limit).
Las cadenas comparten sus finales, así que guardar la longitud ya calculada de cada número ahorra mucho trabajo. Por el camino, los términos pueden superar el límite; usa enteros de 64 bits.
Entrada
limit: el mayor número inicial que hay que probar.
Salida
Devuelve el número inicial cuya cadena tiene más términos (contando el inicial y el 1 final). Si hay empate, devuelve el menor de ellos.
Restricciones
1 ≤ limit ≤ 100,000
Ejemplos
Entrada:
limit = 6
Salida esperada:
expected = 6
Entrada:
long long limit = 6;
Salida esperada:
long long expected = 6;
Entrada:
long limit = 6;
Salida esperada:
long expected = 6;
Explicación
Las cadenas de 1 a 6 tienen 1, 2, 8, 3, 6 y 9 términos, así que la respuesta es 6.
Entrada:
limit = 10
Salida esperada:
expected = 9
Entrada:
long long limit = 10;
Salida esperada:
long long expected = 9;
Entrada:
long limit = 10;
Salida esperada:
long expected = 9;
Explicación
9 da 20 términos (9, 28, 14, 7, ...), más que cualquier otro inicio hasta 10, así que la respuesta es 9.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Primero cuenta los términos de una sola cadena, incluidos el inicial y el 1.
Pista 2
Cuando una cadena llegue a un número cuya longitud ya conoces, suma en lugar de seguir.
Pista 3
Cambia el mejor inicio solo cuando una longitud sea estrictamente mayor.
Complejidad esperada
tiempo O(limit × average new steps), espacio extra O(limit)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.