Todos os desafios
Médio 0 resolvidos 0% de aceitação

Maior sequência de Collatz

Encontre, até um limite, o número inicial cuja sequência de Collatz é a mais longa.

O que você vai aprender

  • Gerar uma sequência de Collatz
  • Guardar resultados em cache para evitar trabalho repetido
  • Desempatar pelo menor valor

Problema

Ver original (inglês)

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

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

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

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.