Problema
A partir de qualquer n positivo, a regra de Collatz define o próximo termo como n / 2 quando n é par e 3n + 1 quando n é ímpar, e a sequência para quando chega a 1. A sequência do 6 é 6, 3, 10, 5, 16, 8, 4, 2, 1: nove termos. Entre todos os números iniciais de 1 a limit, encontre o que gera mais termos.
Implemente longest_collatz_chain(limit).
As sequências compartilham os finais, então guardar o comprimento já encontrado para cada número economiza muito trabalho. Os termos intermediários podem passar do limite; use inteiros de 64 bits.
Entrada
limit: o maior número inicial a testar.
Saída
Retorne o número inicial cuja sequência tem mais termos (contando o início e o 1 final). Em caso de empate, retorne o menor deles.
Restrições
1 ≤ limit ≤ 100 000
Exemplos
Entrada:
limit = 6
Saída esperada:
expected = 6
Entrada:
long long limit = 6;
Saída esperada:
long long expected = 6;
Entrada:
long limit = 6;
Saída esperada:
long expected = 6;
Explicação
Os comprimentos das sequências de 1 a 6 são 1, 2, 8, 3, 6 e 9 termos, então a resposta é 6.
Entrada:
limit = 10
Saída esperada:
expected = 9
Entrada:
long long limit = 10;
Saída esperada:
long long expected = 9;
Entrada:
long limit = 10;
Saída esperada:
long expected = 9;
Explicação
O 9 gera 20 termos (9, 28, 14, 7, ...), mais que qualquer outro início até 10, então a resposta é 9.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Primeiro, conte os termos de uma única sequência, incluindo o início e o 1.
Dica 2
Quando uma sequência chegar a um número cujo comprimento você já conhece, some em vez de continuar.
Dica 3
Só substitua o melhor início quando um comprimento for estritamente maior.
Complexidade esperada
tempo O(limit × average new steps), espaço extra O(limit)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.