Happy Number
Parti da un intero positivo n e sostituiscilo ripetutamente con la somma dei quadrati delle sue cifre. Ad esempio, 12 diventa 1² + 2² = 5. Se questo processo raggiunge 1, n è un numero felice; altrimenti continua a girare all'infinito attraverso numeri che non includono mai 1. Restituisci true se n è felice e false se non lo è.
Funzione
- ninteger
- l'intero positivo da testare
- Restituisceboolean
- vero se ripetere la somma dei quadrati delle cifre raggiunge 1, falso se entra in un ciclo infinito
Vincoli
1 ≤ n ≤ 231-1
Esempi
- Input
- n = 7
- Output
- true
- Spiegazione
- 7 diventa 49, poi 4² + 9² = 97, poi 130, poi 10, poi 1. Il processo raggiunge
1, quindi 7 è felice.
- Input
- n = 2
- Output
- false
- Spiegazione
- 2 diventa 4, 16, 37, 58, 89, 145, 42, 20 e poi di nuovo 4. Da lì gli stessi otto numeri si ripetono all'infinito e non raggiungono mai
1.
- Input
- n = 100
- Output
- true
- Spiegazione
- 1² + 0² + 0² = 1, quindi 100 raggiunge
1dopo un passaggio.
+16 test nascosti all’invio
Per approfondire
Come conteresti rapidamente i numeri felici da 1 a 10^6, riutilizzando le risposte per i numeri inferiori a 1000 invece di ripartire da zero per ogni numero?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Prova a eseguire a mano alcuni inizi. 7 raggiunge 1 in cinque passaggi, mentre 2 torna a 4 dopo otto passaggi. Cosa ti dice il fatto che un numero ritorni?
Ogni valore dipende solo da quello che lo precede, quindi, una volta che un numero si ripete, tutto il tratto successivo si ripete all’infinito. La domanda diventa: il percorso raggiunge 1 prima di raggiungere un numero che ha già incontrato?
Tieni un insieme dei numeri che hai visitato e fermati a 1 o quando incontri un numero già visto. Per usare una memoria costante, fai partire due camminatori da
n, uno che compie un passo per turno e l’altro due; possono incontrarsi solo all’interno di un ciclo.
Soluzione
Il percorso non può mai protrarsi all'infinito. Un numero di 10 cifre corrisponde al massimo a 10 × 81 = 810, e un numero inferiore a 1000 corrisponde al massimo a 3 × 81 = 243, quindi dopo un passaggio il percorso rimane tra meno di 1000 valori e deve raggiungere 1 o ripetere un numero. Questo trasforma il problema in un rilevamento dei cicli: ricorda ciò che hai già visto, oppure fai avanzare un camminatore lento e uno veloce e verifica se si incontrano.
Ricorda ogni numero che hai visto
Intuizione
Percorri la sequenza e conserva ogni numero in un insieme hash. Prima di passare da un numero al successivo, controlla se è già nell’insieme. Per 2, l’insieme si riempie con 2, 4, 16, 37, 58, 89, 145, 42 e 20, e il valore successivo è 4, che è già presente: il percorso ha chiuso un ciclo senza incontrare 1, quindi 2 non è felice. Raggiungere 1 termina il percorso con true.
Questo è corretto perché il numero successivo dipende solo da quello corrente. Quando un numero ricompare, tutto ciò che segue si ripete esattamente, quindi non può comparire nessun nuovo numero e 1 non comparirà mai.
Il percorso è breve. Il primo passaggio legge le O(log n) cifre di n, e ogni valore successivo è minore di 1000, dove nessun percorso visita più di 20 numeri diversi prima di raggiungere 1 o ripetersi. L’insieme contiene questi numeri. Il codice C usa un array di flag con 1000 voci come insieme e inizia a registrare dopo il primo passaggio, quando ogni valore è minore di 1000.
Algoritmo
- Crea un insieme hash vuoto
seen. - Finché
nnon è 1, restituiscifalsesenè inseen. - Altrimenti, aggiungi
naseene sostituiscincon la somma dei quadrati delle sue cifre. - Quando il ciclo termina,
nè 1: restituiscitrue.
def digitSquareSum(n):
total = 0
while n > 0:
digit = n % 10
total += digit * digit
n //= 10
return total
def isHappy(n):
seen = set()
while n != 1:
if n in seen:
return False # back at an earlier number: a loop without 1
seen.add(n)
n = digitSquareSum(n)
return TrueCamminatori veloci e lenti (rilevamento dei cicli di Floyd)
Intuizione
Immagina ogni numero come un nodo con una freccia che punta alla somma dei quadrati delle sue cifre. Seguendo le frecce da n, si arriva a 1, la cui freccia punta di nuovo a 1, oppure si finisce in un ciclo. Questa è la struttura di una lista concatenata che può contenere un ciclo, e l’algoritmo di Floyd rileva un ciclo senza memorizzare nulla: slow avanza di un passo a ogni iterazione e fast ne avanza due.
Se il ciclo non contiene 1, entrambi i cursori finiscono per girarci intorno e, a ogni iterazione, fast guadagna un passo su slow, quindi la distanza si riduce di uno finché non si trovano sullo stesso numero. Per 2 si incontrano su 42 dopo sette iterazioni. Se il percorso raggiunge 1, fast ci arriva per primo e vi rimane, perché la somma per 1 è 1. Quindi fermati quando fast è 1 o quando i cursori si incontrano, e rispondi se fast è 1.
Per 7, slow passa per 7, 49, 97, mentre fast passa per 49, 130, 1, e il ciclo si ferma con fast su 1. Il numero di iterazioni è al massimo un piccolo multiplo della lunghezza del percorso, quindi il tempo è pari a quello della versione con insieme, e la memoria occupata è di due interi.
Algoritmo
- Scrivi una funzione ausiliaria che restituisce la somma dei quadrati delle cifre di un numero.
- Imposta
slow = ne impostafastal numero di un passo dopon. - Finché
fastnon è 1 eslowè diverso dafast, fai avanzareslowdi un passo efastdi due passi. - Restituisci se
fastè 1.
def digitSquareSum(n):
total = 0
while n > 0:
digit = n % 10
total += digit * digit
n //= 10
return total
def isHappy(n):
slow = n
fast = digitSquareSum(n)
# fast moves two steps for every step of slow; they meet only inside a loop.
while fast != 1 and slow != fast:
slow = digitSquareSum(slow)
fast = digitSquareSum(digitSquareSum(fast))
return fast == 1
Trappole e casi limite
L’aritmetica delle cifre è semplice. La maggior parte degli errori riguarda il momento in cui il ciclo si ferma.
- Continuare il ciclo finché il valore non è 1, senza altre condizioni di uscita. Per 2, il ciclo non termina mai.
- Iniziare con
slowefastsullo stesso numero e verificareslow != fastprima della prima mossa. Il ciclo non viene mai eseguito e 7 risulta infelice. Inizia confastun passo avanti oppure sposta entrambi prima del primo confronto. - Restituire
slow == 1nella versione di Floyd.fastraggiunge 1 per primo e il ciclo si ferma subito, mentreslowpuò essere ancora su 97. - Sommare le cifre invece dei loro quadrati, oppure elevare al quadrato l’intero numero. Per 12, il valore successivo è
1² + 2² = 5, non 3 e nemmeno 144. - Dichiarare
ninfelice ogni volta che i due puntatori si incontrano. 1 corrisponde a sé stesso, quindi i puntatori si incontrano anche su 1; controlla dove si sono incontrati oppure fermati non appenafastè 1.
Domande frequenti4
Perché il processo raggiunge sempre 1 o un ciclo?
Un numero con d cifre corrisponde al massimo a 81 × d, quindi i numeri grandi si riducono rapidamente: qualsiasi valore iniziale fino a 2^31-1 scende sotto 1000 dopo un passaggio, e un numero inferiore a 1000 corrisponde al massimo a 243. La sequenza rimane confinata tra meno di 1000 valori, quindi deve ripeterne uno e, da quel momento, entra in un ciclo. 1 è l’unico numero che corrisponde a se stesso.
Qual è la complessità temporale di Happy Number?
Il primo passaggio legge le cifre di n in numero O(log n). Ogni valore successivo è inferiore a 1000 e il percorso si ripete entro al massimo 20 numeri, quindi il tempo totale è O(log n). La versione con insieme hash memorizza i numeri visitati; la versione di Floyd usa spazio O(1).
Perché tutti i numeri infelici finiscono per arrivare a 4?
Controllando tutti i numeri inferiori a 1000 si osserva esattamente un ciclo che non passa per 1: 4, 16, 37, 58, 89, 145, 42, 20 e poi di nuovo 4. Poiché ogni valore iniziale scende sotto 1000, ogni numero infelice finisce in quel ciclo. Una soluzione può fermarsi appena incontra 4, ma ciò si basa su un fatto che dovresti giustificare durante un colloquio; l’insieme e il metodo di Floyd non richiedono questa conoscenza.
In che modo il numero felice è correlato al ciclo di una lista concatenata?
Entrambi chiedono se, seguendo una freccia da ciascun elemento, si torna mai a un elemento già visitato. In Happy Number, la freccia è la somma dei quadrati delle cifre; in una lista concatenata, è il puntatore next. Ecco perché i camminatori veloci e lenti di Floyd risolvono entrambi i problemi usando una quantità costante di memoria.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def isHappy(n):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
n = 7
Atteso
true