Problema
Parti da un intero positivo e sostituiscilo con la somma dei quadrati delle sue cifre. Poi ripeti l'operazione. Se prima o poi il numero diventa 1, il numero di partenza è felice. Altrimenti il procedimento finisce in un ciclo che non contiene mai 1, e il numero è infelice. Per esempio 7 → 49 → 97 → 130 → 10 → 1, quindi 7 è felice.
Implementa happy_number(n).
Ti serve un modo per accorgerti che la sequenza ha cominciato a ripetersi, così il ciclo si ferma anche sui numeri infelici.
Input
n: il numero di partenza.
Output
Restituisci true se il procedimento arriva a 1, altrimenti false. Il numero 1 è felice.
Vincoli
1 ≤ n ≤ 10^9
Esempi
Input:
n = 19
Output atteso:
expected = True
Input:
long long n = 19;
Output atteso:
bool expected = true;
Input:
long n = 19;
Output atteso:
bool expected = true;
Spiegazione
1² + 9² = 82, poi 8² + 2² = 68, poi 6² + 8² = 100, poi 1² + 0² + 0² = 1, quindi 19 è felice: true.
Input:
n = 4
Output atteso:
expected = False
Input:
long long n = 4;
Output atteso:
bool expected = false;
Input:
long n = 4;
Output atteso:
bool expected = false;
Spiegazione
4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 si ripete senza mai arrivare a 1, quindi la risposta è false.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Scrivi una funzione di supporto che trasforma un numero nella somma dei quadrati delle sue cifre.
Suggerimento 2
Un numero infelice prima o poi ripete un valore già prodotto; memorizza i valori che hai già visto.
Suggerimento 3
La sequenza scende molto presto sotto qualche centinaio, quindi l'insieme resta piccolo.
Complessità attesa
O(log n) passi per numero, spazio aggiuntivo O(1) con due puntatori
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.