Problem
Beginne mit einer positiven ganzen Zahl und ersetze sie durch die Summe der Quadrate ihrer Ziffern. Wiederhole das immer wieder. Wird die Zahl irgendwann zu 1, ist die Startzahl fröhlich. Andernfalls gerät der Vorgang in einen Kreislauf, der die 1 nie enthält, und die Zahl ist traurig. Zum Beispiel gilt 7 → 49 → 97 → 130 → 10 → 1, also ist 7 fröhlich.
Implementiere happy_number(n).
Du brauchst eine Möglichkeit zu erkennen, dass sich die Folge zu wiederholen beginnt, damit die Schleife auch bei traurigen Zahlen endet.
Eingabe
n: Die Startzahl.
Ausgabe
Gib true zurück, wenn der Vorgang 1 erreicht, sonst false. Die 1 selbst ist fröhlich.
Einschränkungen
1 ≤ n ≤ 10^9
Beispiele
Eingabe:
n = 19
Erwartete Ausgabe:
expected = True
Eingabe:
long long n = 19;
Erwartete Ausgabe:
bool expected = true;
Eingabe:
long n = 19;
Erwartete Ausgabe:
bool expected = true;
Erläuterung
1² + 9² = 82, dann 8² + 2² = 68, dann 6² + 8² = 100, dann 1² + 0² + 0² = 1, also ist 19 fröhlich: true.
Eingabe:
n = 4
Erwartete Ausgabe:
expected = False
Eingabe:
long long n = 4;
Erwartete Ausgabe:
bool expected = false;
Eingabe:
long n = 4;
Erwartete Ausgabe:
bool expected = false;
Erläuterung
4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 wiederholt sich, ohne jemals 1 zu erreichen, also lautet die Antwort false.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Schreib eine Hilfsfunktion, die eine Zahl auf die Summe der Quadrate ihrer Ziffern abbildet.
Hinweis 2
Eine traurige Zahl erzeugt irgendwann einen Wert, den sie schon einmal hatte; merke dir die bisherigen Werte.
Hinweis 3
Die Folge fällt sehr schnell unter ein paar Hundert, daher bleibt die Menge klein.
Erwartete Komplexität
Zeit O(log n) Schritte pro Zahl, zusätzlicher Speicher O(1) mit zwei Zeigern
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.