Einfach 0 gelöst 0% Erfolgsquote

Fröhliche Zahl

Entscheide, ob man durch wiederholtes Aufsummieren der Ziffernquadrate einer Zahl bei 1 landet.

Das lernst du

  • Die Summe der Ziffernquadrate berechnen
  • Eine sich wiederholende Folge mit einer Menge oder zwei Zeigern erkennen
  • Eine Schleife bei einer von zwei Bedingungen beenden

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

Beispiel 1
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.

Beispiel 2
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.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.