Tutte le sfide
Media 0 risolte 0% di accettazione

La successione di Collatz più lunga

Trova il numero di partenza, fino a un limite, con la successione di Collatz più lunga.

Cosa imparerai

  • Generare una successione di Collatz
  • Memorizzare i risultati per non ripetere il lavoro
  • Risolvere le parità scegliendo il valore più piccolo

Problema

Partendo da un qualsiasi n positivo, la regola di Collatz dice che il termine successivo è n / 2 se n è pari e 3n + 1 se n è dispari; la successione si ferma quando arriva a 1. La successione di 6 è 6, 3, 10, 5, 16, 8, 4, 2, 1: nove termini. Tra tutti i numeri di partenza da 1 a limit, trova quello con più termini.

Implementa longest_collatz_chain(limit).

Molte successioni finiscono allo stesso modo, quindi ricordare la lunghezza già trovata per ogni numero fa risparmiare parecchio lavoro. I termini intermedi possono superare il limite: usa interi a 64 bit.

Input

limit: il numero di partenza più grande da provare.

Output

Restituisci il numero di partenza la cui successione ha più termini (contando il numero iniziale e l'1 finale). In caso di parità, restituisci il più piccolo.

Vincoli

1 ≤ limit ≤ 100 000

Esempi

Esempio 1
Input:
limit = 6

Output atteso:
expected = 6
Input:
long long limit = 6;

Output atteso:
long long expected = 6;
Input:
long limit = 6;

Output atteso:
long expected = 6;

Spiegazione

Le successioni da 1 a 6 hanno 1, 2, 8, 3, 6 e 9 termini, quindi la risposta è 6.

Esempio 2
Input:
limit = 10

Output atteso:
expected = 9
Input:
long long limit = 10;

Output atteso:
long long expected = 9;
Input:
long limit = 10;

Output atteso:
long expected = 9;

Spiegazione

9 dà 20 termini (9, 28, 14, 7, ...), più di qualsiasi altro numero di partenza fino a 10, quindi la risposta è 9.

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

Conta prima i termini di una sola successione, compresi il numero iniziale e l'1.

Suggerimento 2

Quando una successione arriva a un numero di cui conosci già la lunghezza, somma invece di proseguire.

Suggerimento 3

Sostituisci il miglior numero di partenza solo quando la lunghezza è strettamente maggiore.

Complessità attesa

tempo O(limit × average new steps), cioè limit per il numero medio di passi nuovi, spazio aggiuntivo O(limit)

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.