Sum of Digits
Ti viene dato un intero non negativo n. Restituisci la somma delle sue cifre decimali. Per esempio, le cifre di 482 sono 4, 8 e 2, quindi la risposta è 14.
Funzione
- ninteger
- l’intero non negativo le cui cifre sommi
- Restituisceinteger
- la somma delle cifre decimali di n
Vincoli
0 ≤ n ≤ 231-1
Esempi
- Input
- n = 9045
- Output
- 18
- Spiegazione
- Le cifre di
9045sono 9, 0, 4 e 5, e9 + 0 + 4 + 5 = 18. Lo zero non aggiunge nulla, ma conta comunque come cifra.
- Input
- n = 7
- Output
- 7
- Spiegazione
- Un numero a una cifra è uguale alla somma delle sue cifre, quindi
7dà7.
+15 test nascosti all’invio
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Come trovi l'ultima cifra di un numero con una sola operazione aritmetica?
L'ultima cifra è
n % 10e la divisione intera per 10 la rimuove. Ogni coppia di operazioni ti fornisce una cifra.Mantieni un totale progressivo. Mentre
nè maggiore di 0, aggiungin % 10a esso e dividinper 10, arrotondando per difetto.
Soluzione
Un numero non ti fornisce le sue cifre una alla volta: devi scomporlo. Puoi convertirlo in testo e leggere i caratteri, oppure usare le due operazioni aritmetiche che estraggono l’ultima cifra: n % 10 la restituisce e la divisione intera per 10 la rimuove. Entrambi i metodi richiedono un passaggio per cifra, indicato qui sotto con d, e qui d ≤ 10. Il metodo aritmetico non richiede memoria aggiuntiva.
Leggi le cifre come testo
Intuizione
Quando scrivi un numero, vedi già le sue cifre. Trasforma n nel suo testo decimale: 9045 diventa i quattro caratteri 9, 0, 4 e 5; poi scorri i caratteri e aggiungi il valore di ciascuno.
Un carattere non è ancora un numero. Il carattere '4' viene memorizzato come codice 52, quindi lo analizzi oppure sottrai il codice di '0': '4' - '0' = 4. I caratteri cifra hanno codici consecutivi, ed è per questo che la sottrazione funziona per tutte e dieci le cifre.
Il testo ha d caratteri, uno per cifra, quindi il ciclo richiede un tempo O(d), mentre il testo stesso richiede O(d) spazio aggiuntivo.
Algoritmo
- Converti
nnel suo testo decimale. - Imposta
total = 0. - Per ogni carattere, aggiungi il suo valore numerico a
total. - Restituisci
total.
def sumOfDigits(n):
total = 0
for digit in str(n):
total += int(digit)
return totalEstrai l'ultima cifra con % 10
Intuizione
Puoi scomporre un numero senza alcun testo. Il resto di una divisione per 10 è l'ultima cifra: 9045 % 10 = 5. La divisione intera per 10 elimina quella cifra: 9045 / 10 = 904 quando si scarta la parte frazionaria. Ripeti la coppia e le cifre usciranno da destra a sinistra.
Per 9045: aggiungi 5 e tieni 904, aggiungi 4 e tieni 90, aggiungi 0 e tieni 9, aggiungi 9 e tieni 0. Il ciclo si ferma a 0 con un totale di 18. Per n = 0 il ciclo non viene mai eseguito e la risposta è 0, il che è corretto.
Ogni passaggio rimuove una cifra, quindi ci sono d passaggi, tempo O(d) e solo due interi in memoria, spazio O(1). Ogni valore intermedio è minore di n, quindi niente può andare in overflow.
Algoritmo
- Imposta
total = 0. - Mentre
n > 0, aggiungin % 10atotal. - Dividi
nper 10, scartando la parte frazionaria. - Quando
nraggiunge 0, restituiscitotal.
def sumOfDigits(n):
total = 0
while n > 0:
total += n % 10 # last digit
n //= 10 # drop the last digit
return total
Trappole e casi limite
Il ciclo è breve e gli errori riguardano i tipi e l'input più piccolo.
- Usare
/quando il linguaggio esegue una divisione reale. In JavaScript, TypeScript, Lua, PHP e R,9045 / 10è904.5e il ciclo aggiunge quindi frazioni. Arrotonda per difetto conMath.flooromath.floor; in Python usa//, in Dart~/, in PHPintdiv, in R%/%. - Aggiungere caratteri invece di cifre. Il carattere
'7'ha codice 55, non 7. Sottrai'0'oppure analizza prima il carattere. - Iterare finché
n >= 10. Il ciclo si ferma lasciando innla cifra iniziale, senza aggiungerla: quindi9045dà 9 invece di 18. Itera finchén > 0, che restituisce anche 0 quandon = 0. - Stampare numeri grandi come testo in R.
as.character(100000)dà"1e+05", non le sei cifre del numero. Usaformat(n, scientific = FALSE).
Domande frequenti4
Qual è la complessità temporale della somma delle cifre di un numero?
Un passaggio per cifra, quindi O(d), dove d è il numero di cifre. Un numero n ha circa log10(n) + 1 cifre, quindi lo stesso limite viene spesso scritto O(log n). Per un intero a 32 bit sono al massimo 10 passaggi.
Come si ottengono le cifre di un numero senza convertirlo in una stringa?
Usa il resto e la divisione intera per 10. n % 10 è l'ultima cifra e dividere n per 10 scartando il resto elimina quella cifra. Ripeti finché n raggiunge 0 e visiterai ogni cifra da destra a sinistra.
Qual è la radice digitale di un numero?
È ciò che ottieni sommando le cifre più e più volte finché non ne rimane una sola: 9045 dà 18, poi 9. Per un n positivo equivale a 1 + (n-1) % 9, perché ogni numero ha lo stesso resto della somma delle sue cifre quando viene diviso per 9.
È meglio la versione con stringhe o quella aritmetica?
Entrambe sono O(d) ed entrambe sono corrette. La versione con stringhe è più breve da scrivere in molti linguaggi, ma crea una copia delle cifre. La versione aritmetica usa O(1) di memoria aggiuntiva e mostra all’intervistatore che sai come % 10 e / 10 scompongono un numero, cosa utile nei problemi sui palindromi e sull’inversione delle cifre.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def sumOfDigits(n):
# Scrivi il codice quiCaso 1
Caso 2
Input
n = 9045
Atteso
18