Problem
Addiere die Ziffern von n. Hat das Ergebnis mehr als eine Ziffer, addiere erneut dessen Ziffern. Wiederhole dies, bis nur noch eine einzige Ziffer übrig bleibt.
Implementiere digital_root(n).
Eingabe
n: Eine positive ganze Zahl.
Ausgabe
Gib die endgültige einstellige Zahl zurück.
Einschränkungen
1 ≤ n ≤ 10¹⁸
Beispiele
Beispiel 1
Eingabe:
n = 999
Erwartete Ausgabe:
expected = 9Eingabe:
long long n = 999;
Erwartete Ausgabe:
long long expected = 9;Eingabe:
long n = 999;
Erwartete Ausgabe:
long expected = 9;Erläuterung
9 + 9 + 9 = 27, dann 2 + 7 = 9.
Beispiel 2
Eingabe:
n = 38
Erwartete Ausgabe:
expected = 2Eingabe:
long long n = 38;
Erwartete Ausgabe:
long long expected = 2;Eingabe:
long n = 38;
Erwartete Ausgabe:
long expected = 2;Erläuterung
3 + 8 = 11, dann 1 + 1 = 2.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Wiederholtes Addieren der Ziffern reduziert die Zahl irgendwann auf eine Ziffer.
Hinweis 2
Du kannst das wiederholte Summieren simulieren, bis der Wert kleiner als 10 ist.
Hinweis 3
Achte auf sehr große Eingaben; das Verfahren ist einfach, aber mehrere Durchläufe über die Ziffern sind die Hauptarbeit.
Erwartete Komplexität
Zeit O(d log n), zusätzlicher Speicher O(1)