Sum of Digits

Q: 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.

Q: 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.

PrincipianteMatematica e simulazione

+10

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

sumOfDigits(n: integer) → integer

ninteger: l’intero non negativo le cui cifre sommi
Restituisceinteger: la somma delle cifre decimali di n

Vincoli

0 ≤ n ≤ 2³¹-1

Esempi

Input: n = 9045
Output: 18
Spiegazione: Le cifre di 9045 sono 9, 0, 4 e 5, e 9 + 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 7 dà 7.

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

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 n nel 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 total

Estrai 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, aggiungi n % 10 a total.
Dividi n per 10, scartando la parte frazionaria.
Quando n raggiunge 0, restituisci total.

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.5 e il ciclo aggiunge quindi frazioni. Arrotonda per difetto con Math.floor o math.floor; in Python usa //, in Dart ~/, in PHP intdiv, 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 in n la cifra iniziale, senza aggiungerla: quindi 9045 dà 9 invece di 18. Itera finché n > 0, che restituisce anche 0 quando n = 0.
Stampare numeri grandi come testo in R. as.character(100000) dà "1e+05", non le sei cifre del numero. Usa format(n, scientific = FALSE).

Domande frequenti3

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.

def sumOfDigits(n):
    # Scrivi il codice qui

Test #1

Test #2

Argomento

n = 9045

Output atteso