Todos los desafíos
Intermedio 0 resueltos 0% de aceptación

La cadena de Collatz más larga

Encuentra el número inicial, hasta un límite, cuya cadena de Collatz es la más larga.

Lo que aprenderás

  • Generar una cadena de Collatz
  • Guardar resultados para no repetir trabajo
  • Desempatar eligiendo el valor más pequeño

Problema

Ver original (inglés)

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

Ejemplo 1
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.

Ejemplo 2
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.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.