Armstrong Number
Un intero positivo è un numero di Armstrong quando è uguale alla somma delle sue cifre, ciascuna elevata alla potenza del numero di cifre che lo compongono. 153 ha tre cifre e 1^3 + 5^3 + 3^3 = 153, quindi è un numero di Armstrong. Scrivi una funzione che riceva n e restituisca true se è un numero di Armstrong e false altrimenti.
Funzione
- ninteger
- l'intero positivo da verificare
- Restituisceboolean
- true quando n è uguale alla somma delle sue cifre, ciascuna elevata al numero di cifre
Vincoli
1 ≤ n ≤ 109
Esempi
- Input
- n = 153
- Output
- true
- Spiegazione
153ha 3 cifre, quindi ogni cifra viene elevata al cubo:1 + 125 + 27 = 153. La somma restituisce il numero, quindi la risposta ètrue.
- Input
- n = 10
- Output
- false
- Spiegazione
10ha 2 cifre, quindi ogni cifra viene elevata al quadrato:1 + 0 = 1, che non è10. La risposta èfalse.
- Input
- n = 9474
- Output
- true
- Spiegazione
- Con 4 cifre la potenza è 4:
6561 + 256 + 2401 + 256 = 9474, il numero stesso, quindi la risposta ètrue.
+31 test nascosti all’invio
Per approfondire
Solo 31 numeri di Armstrong si trovano tra 1 e 10^9. Riesci a elencarli tutti senza verificare un miliardo di numeri uno per uno?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Prima di poter elevare una cifra a una potenza, ti serve l'esponente. Quante cifre ha
ne come puoi scoprirlo con l'aritmetica?n % 10è l'ultima cifra e la divisione intera per 10 la rimuove. Ripeti finché non rimane nulla: in questo modo visiti ogni cifra e il numero di passaggi è l'esponentek.Conta le cifre in un solo passaggio. Poi estraili di nuovo, aggiungi ciascuna cifra elevata alla potenza
ka un totale a 64 bit e restituisci se il totale è uguale all’originalen.
Soluzione
La definizione è l'algoritmo: trova quante cifre ha n, eleva ogni cifra a quella potenza, somma i risultati e confronta con n. Le insidie sono nei numeri. L'esponente è il numero di cifre di questo specifico n, non un 3 fisso, e la somma può superare un intero a 32 bit: per 999999999 è 9 × 9^9 = 3486784401.
Leggi le cifre dalla stringa
Intuizione
La stringa decimale di n ti fornisce entrambe le cose di cui hai bisogno. La sua lunghezza è l’esponente k e i suoi caratteri sono le cifre. Per 9474 la stringa ha 4 caratteri, quindi sommi 9^4 + 4^4 + 7^4 + 4^4.
Riconverti ogni carattere nella cifra corrispondente, elevi la cifra alla potenza k e la aggiungi a un totale progressivo. n è un numero di Armstrong esattamente quando il totale finale è uguale a n.
Mantieni il totale in un intero a 64 bit. n rientra in 32 bit, ma la somma non necessariamente: 999999999 dà 3486784401, che supera il limite a 32 bit di 2147483647. Calcolare una potenza con un ciclo di k moltiplicazioni richiede k passaggi per cifra, quindi il controllo è O(k²) con k approssimativamente uguale a log n. In questo caso si tratta al massimo di 100 moltiplicazioni e la stringa occupa k caratteri di memoria.
Algoritmo
- Converti
nnella sua stringa decimale e impostakalla sua lunghezza. - Imposta un
totala 64 bit su0. - Per ogni carattere, trasformalo nella cifra
de aggiungid^katotal, moltiplicando numeri interi anziché chiamare una funzione di potenza in virgola mobile. - Restituisci se
totalè uguale an.
def isArmstrong(n):
digits = str(n)
k = len(digits)
total = 0
for ch in digits:
total += int(ch) ** k
return total == nSepara le cifre e consulta le loro potenze
Intuizione
La sola aritmetica fa lo stesso lavoro senza una stringa. m % 10 è l’ultima cifra di m e la divisione intera per 10 la rimuove, quindi un ciclo che divide per 10 finché non resta nulla conta le cifre. 9474 diventa 947, 94, 9, 0: quattro passaggi, quindi k = 4.
Esistono solo dieci cifre, quindi crea una tabella powers[d] = d^k per d da 0 a 9 prima di sommare qualsiasi valore. Per ogni cifra serve così una sola ricerca nella tabella invece di k moltiplicazioni. Il controllo scende a un tempo O(log n) e la tabella ha una dimensione fissa di dieci elementi, quindi occupa uno spazio O(1).
Il secondo ciclo estrae di nuovo le cifre e aggiunge powers[m % 10] al totale. Ogni termine è zero o positivo, quindi il totale non diminuisce mai e, non appena supera n, la risposta è false. Per 999999999 succede dopo tre cifre, quando si raggiunge 3 × 387420489 = 1162261467. La tabella ha comunque bisogno di 64 bit, perché n = 10^9 ha dieci cifre e 9^10 = 3486784401.
Algoritmo
- Conta le cifre di
ndividendo una copia per 10 finché non raggiunge 0; chiama il conteggiok. - Imposta
powers[d] = d^kper ogni cifradda 0 a 9, usando interi a 64 bit. - Dividi di nuovo una copia fresca di
nper 10, aggiungendopowers[m % 10]atotala ogni passaggio. - Se
totalsuperan, restituisci subitofalse. - Dopo l'ultima cifra, restituisci se
totalè uguale an.
def isArmstrong(n):
# Count the digits: k is the exponent.
k = 0
m = n
while m > 0:
k += 1
m //= 10
# powers[d] = d^k for the ten possible digits.
powers = [d ** k for d in range(10)]
total = 0
m = n
while m > 0:
total += powers[m % 10]
if total > n:
return False # the total only grows
m //= 10
return total == n
Trappole e casi limite
La formula è breve, quindi i bug derivano dai numeri che la circondano.
- Un esponente fisso di 3. Accetta
153e370, ma rifiuta9474e tutti i numeri di una cifra superiori a 1, poiché7^3 = 343. - Una somma a 32 bit.
999999999dà come somma3486784401e la voce della tabella9^10è lo stesso numero. In C, quell'overflow ha un comportamento indefinito; Java e C# vanno in overflow producendo un numero negativo, mentre una build di debug di Rust genera un panic. Usalong,long longoi64. - Potenze in virgola mobile.
powin C eMath.powin Java restituiscono undouble. Alcuni runtime C hanno restituito un valore leggermente inferiore a un numero intero, come24.999...per5^2, che una conversione tronca a24. Moltiplica invece numeri interi in un ciclo. - Confronto con il valore sbagliato. I cicli sulle cifre dividono
nfino a portarlo a 0, quindi lavora su una copia e confronta il totale con il valore originale. - Notazione scientifica. In R,
as.character(1e9)è"1e+09", cioè cinque caratteri; perciò, una soluzione in R basata su stringhe formatta consprintf("%.0f", n).
Domande frequenti4
Che cos'è un numero di Armstrong?
Un numero di Armstrong, chiamato anche numero narcisistico, è uguale alla somma delle proprie cifre, ciascuna elevata alla potenza pari al numero di cifre. 153 lo è perché 1^3 + 5^3 + 3^3 = 153, e 9474 lo è perché 9^4 + 4^4 + 7^4 + 4^4 = 9474. Tutti i numeri di una cifra soddisfano questa proprietà, poiché d^1 = d.
Quanti numeri di Armstrong ci sono?
In base 10 ci sono esattamente 88 numeri positivi di questo tipo, e il più grande ha 39 cifre. L’elenco è finito perché un numero con k cifre è almeno 10^(k-1), mentre la somma delle potenze delle sue cifre è al massimo k × 9^k, e a partire da 61 cifre la somma non può mai raggiungerlo. Tra 1 e 10^9 ce ne sono 31.
Perché il controllo del numero di Armstrong richiede un intero a 64 bit?
L’input rientra in 32 bit, ma la somma delle cifre elevate a potenza può essere diverse volte più grande del numero. 999999999 dà 9 × 9^9 = 3486784401, che supera 2^31-1 = 2147483647. In quel caso, un totale a 32 bit va in overflow, quindi mantieni il totale e le potenze in un tipo a 64 bit.
Qual è la complessità temporale della verifica di un numero di Armstrong?
n ha circa log n cifre, al massimo 10 in questo caso. Estrarre le cifre e cercare ogni potenza in una tabella di dieci elementi richiede un tempo O(log n) e uno spazio O(1). Ricalcolare d^k con un ciclo per ogni cifra porta il tempo a O(log² n), comunque veloce per una dimensione simile.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def isArmstrong(n):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
n = 153
Atteso
true