Sum of Digits

Q: Wie hoch ist die Zeitkomplexität beim Addieren der Ziffern einer Zahl?

Ein Schritt pro Ziffer, also O(d) , wobei d die Anzahl der Ziffern ist. Eine Zahl n hat etwa log10(n) + 1 Ziffern, daher wird dieselbe Schranke oft als O(log n) geschrieben. Für eine 32-Bit-Ganzzahl sind das höchstens 10 Schritte.

Q: Wie erhält man die Ziffern einer Zahl, ohne sie in eine Zeichenfolge umzuwandeln?

Verwende den Rest und die ganzzahlige Division durch 10. n % 10 ist die letzte Ziffer, und wenn du n durch 10 teilst und den Rest verwirfst, fällt diese Ziffer weg. Wiederhole das, bis n den Wert 0 erreicht, und du durchläufst alle Ziffern von rechts nach links.

Q: Ist die Zeichenkettenversion oder die arithmetische Version besser?

Beide sind O(d) und beide sind korrekt. Die String-Version ist in vielen Sprachen kürzer zu schreiben, erstellt aber eine Kopie der Ziffern. Die arithmetische Version benötigt O(1) zusätzlichen Speicher und zeigt dem Interviewer, dass du weißt, wie % 10 und / 10 eine Zahl in ihre Bestandteile zerlegen – das kommt bei Palindrom- und Ziffernumkehrproblemen wieder zum Einsatz.

EinsteigerMathe und Simulation

+10

Du erhältst eine nichtnegative ganze Zahl n. Gib die Summe ihrer Dezimalziffern zurück. Die Ziffern von 482 sind zum Beispiel 4, 8 und 2, also lautet das Ergebnis 14.

Funktion

sumOfDigits(n: integer) → integer

ninteger: die nichtnegative ganze Zahl, deren Ziffern du addierst
Gibt zurückinteger: die Summe der Dezimalziffern von n

Einschränkungen

0 ≤ n ≤ 2³¹-1

Beispiele

Eingabe: n = 9045
Ausgabe: 18
Erklärung: Die Ziffern von 9045 sind 9, 0, 4 und 5, und 9 + 0 + 4 + 5 = 18. Die Null trägt nichts zur Summe bei, zählt aber trotzdem als Ziffer.

Eingabe: n = 7
Ausgabe: 7
Erklärung: Eine einstellige Zahl ist ihre eigene Quersumme, daher ergibt 7 7.

+15 versteckte Tests beim Einreichen

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Eine Zahl gibt dir ihre Ziffern nicht einzeln aus; du musst sie zerlegen. Du kannst sie in Text umwandeln und die Zeichen lesen oder die beiden Rechenschritte verwenden, mit denen du die letzte Ziffer abtrennst: n % 10 liefert sie, und die ganzzahlige Division durch 10 entfernt sie. Beide benötigen einen Schritt pro Ziffer, hier mit d bezeichnet, und d ≤ 10. Die arithmetische Variante benötigt keinen zusätzlichen Speicher.

Lies die Ziffern als Text

Idee

Wenn du eine Zahl aufschreibst, siehst du ihre Ziffern bereits. Wandle n in seinen Dezimaltext um: Aus 9045 werden die vier Zeichen 9, 0, 4 und 5. Gehe dann die Zeichen durch und addiere den Wert jedes einzelnen.

Ein Zeichen ist noch keine Zahl. Das Zeichen '4' wird als Code 52 gespeichert. Du kannst es also parsen oder den Code von '0' subtrahieren: '4' - '0' = 4. Die Codes der Ziffernzeichen sind aufeinanderfolgend, weshalb diese Subtraktion für alle zehn funktioniert.

Der Text hat d Zeichen, eines pro Ziffer. Daher benötigt die Schleife O(d) Zeit, und der Text selbst benötigt O(d) zusätzlichen Speicherplatz.

Algorithmus

Wandle n in seinen Dezimaltext um.
Setze total = 0.
Addiere für jedes Zeichen seinen Ziffernwert zu total.
Gib total zurück.

def sumOfDigits(n):
    total = 0
    for digit in str(n):
        total += int(digit)
    return total

Die letzte Ziffer mit % 10 abtrennen

Idee

Du kannst eine Zahl ohne Text auseinandernehmen. Der Rest einer Division durch 10 ist die letzte Ziffer: 9045 % 10 = 5. Bei der ganzzahligen Division durch 10 wird diese Ziffer verworfen: 9045 / 10 = 904, wenn der Bruchteil weggelassen wird. Wiederhole das Paar, und die Ziffern kommen von rechts nach links heraus.

Für 9045: Addiere 5 und behalte 904, addiere 4 und behalte 90, addiere 0 und behalte 9, addiere 9 und behalte 0. Die Schleife endet bei 0 mit einer Summe von 18. Für n = 0 wird die Schleife nie ausgeführt, und das Ergebnis ist 0, was korrekt ist.

Bei jedem Schritt wird eine Ziffer entfernt, also gibt es d Schritte, eine Laufzeit von O(d) und nur zwei Ganzzahlen im Speicher, also einen Speicherbedarf von O(1). Jeder Zwischenwert ist kleiner als n, daher kann nichts überlaufen.

Algorithmus

Setze total = 0.
Solange n > 0 gilt, addiere n % 10 zu total.
Teile n durch 10 und lasse den Bruchteil weg.
Wenn n 0 erreicht, gib total zurück.

def sumOfDigits(n):
    total = 0
    while n > 0:
        total += n % 10  # last digit
        n //= 10         # drop the last digit
    return total

Stolperfallen und Grenzfälle

Die Schleife ist kurz, und die Fehler betreffen die Typen und die kleinste Eingabe.

/ zu verwenden, obwohl die Sprache damit eine echte Division meint. In JavaScript, TypeScript, Lua, PHP und R ist 9045 / 10 gleich 904.5, und die Schleife addiert dann Bruchteile. Runde mit Math.floor oder math.floor ab; verwende in Python //, in Dart ~/, in PHP intdiv und in R %/%.
Zeichen statt Ziffern zu addieren. Das Zeichen '7' hat den Code 55, nicht 7. Ziehe '0' ab oder parse das Zeichen zuerst.
Mit n >= 10 zu iterieren. Die Schleife endet dann, während die führende Ziffer noch in n steht, und addiert sie nie, sodass 9045 9 statt 18 ergibt. Iteriere mit n > 0; damit wird auch für n = 0 0 zurückgegeben.
Große Zahlen in R als Text auszugeben. as.character(100000) ergibt "1e+05", nicht die sechs Ziffern der Zahl. Verwende format(n, scientific = FALSE).

Häufige Fragen4

Wie hoch ist die Zeitkomplexität beim Addieren der Ziffern einer Zahl?

Ein Schritt pro Ziffer, also O(d), wobei d die Anzahl der Ziffern ist. Eine Zahl n hat etwa log10(n) + 1 Ziffern, daher wird dieselbe Schranke oft als O(log n) geschrieben. Für eine 32-Bit-Ganzzahl sind das höchstens 10 Schritte.

Wie erhält man die Ziffern einer Zahl, ohne sie in eine Zeichenfolge umzuwandeln?

Verwende den Rest und die ganzzahlige Division durch 10. n % 10 ist die letzte Ziffer, und wenn du n durch 10 teilst und den Rest verwirfst, fällt diese Ziffer weg. Wiederhole das, bis n den Wert 0 erreicht, und du durchläufst alle Ziffern von rechts nach links.

Was ist die digitale Wurzel einer Zahl?

Es ist das Ergebnis, wenn du die Ziffern immer wieder addierst, bis eine Ziffer übrig bleibt: 9045 ergibt 18 und dann 9. Für ein positives n ist es gleich 1 + (n-1) % 9, weil jede Zahl bei der Division durch 9 denselben Rest lässt wie ihre Quersumme.

Ist die Zeichenkettenversion oder die arithmetische Version besser?

Beide sind O(d) und beide sind korrekt. Die String-Version ist in vielen Sprachen kürzer zu schreiben, erstellt aber eine Kopie der Ziffern. Die arithmetische Version benötigt O(1) zusätzlichen Speicher und zeigt dem Interviewer, dass du weißt, wie % 10 und / 10 eine Zahl in ihre Bestandteile zerlegen – das kommt bei Palindrom- und Ziffernumkehrproblemen wieder zum Einsatz.

Python

def sumOfDigits(n):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Eingabe

n = 9045

Erwartet