Tutte le sfide
Facile 0 risolte 0% di accettazione

Numero felice

Stabilisci se, sommando ripetutamente i quadrati delle cifre di un numero, si arriva a 1.

Cosa imparerai

  • Calcolare la somma dei quadrati delle cifre
  • Accorgersi che una sequenza si ripete con un insieme o con due puntatori
  • Fermare un ciclo al verificarsi di una tra due condizioni

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

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

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

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.