Problema
Parti da n. Se è pari, dividilo per 2; se è dispari, moltiplicalo per 3 e aggiungi 1. Ripeti fino a quando il valore diventa 1. Includi sia il valore iniziale che il valore finale 1 nella tua risposta.
Implementa collatz_sequence(n).
Input
n: L'intero positivo di partenza.
Output
Restituisci l'intera sequenza in ordine.
Vincoli
1 ≤ n ≤ 10.000. Gli input in questo intervallo raggiungono sempre 1 seguendo questa regola; tutti i valori della sequenza rientrano in un intero con segno a 64 bit.
Esempi
Input:
n = 6
Output atteso:
expected = [6, 3, 10, 5, 16, 8, 4, 2, 1]Input:
long long n = 6;
Output atteso:
std::vector<long long> expected = {6, 3, 10, 5, 16, 8, 4, 2, 1};Input:
long n = 6;
Output atteso:
long[] expected = new long[] {6, 3, 10, 5, 16, 8, 4, 2, 1};Spiegazione
6 è pari, quindi diventa 3. Poi 3 diventa 10. Continua ad applicare la regola fino a 1.
Input:
n = 1
Output atteso:
expected = [1]Input:
long long n = 1;
Output atteso:
std::vector<long long> expected = {1};Input:
long n = 1;
Output atteso:
long[] expected = new long[] {1};Spiegazione
Il valore iniziale è già 1, quindi non sono necessarie trasformazioni.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
La sequenza si genera applicando più volte una regola in base al fatto che il numero corrente sia pari o dispari.
Suggerimento 2
Aggiungi ogni nuovo valore fino a raggiungere 1.
Suggerimento 3
Fai attenzione: sia il valore iniziale sia l'1 finale devono comparire nel risultato.
Complessità attesa
O(k) time, O(k) extra space, where k is the sequence length
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.