In der Serie "Named Problems" stelle ich dir klassische, namentlich bekannte Algorithmus-Probleme vor, die seit Jahrzehnten in Ausbildung, Studium und Interviews verwendet werden. Anhand verständlicher Problemstellungen wie FizzBuzz, Türme von Hanoi oder dem Sieb des Eratosthenes lernst du hier, algorithmisch zu denken, Lösungsstrategien zu entwickeln und diese sauber in Java umzusetzen.

„Happy Numbers“ sind ein klassisches Problem aus Programmier-Interviews und Übungsplattformen. Es wirkt auf den ersten Blick wie Zahlenspielerei, ist aber perfekt, um Iteration, Zustandsveränderung und Schleifen sauber zu üben.

Die Idee: Du nimmst eine Zahl, zerlegst sie in Ziffern, quadrierst jede Ziffer und addierst alles. Mit dem Ergebnis machst du weiter. Irgendwann passiert etwas: Entweder landest du bei 1 (dann ist die Zahl happy), oder du läufst in eine Schleife und wiederholst Werte (dann ist sie nicht happy).

In diesem Artikel lernst du, wie du den Zustand (die aktuelle Zahl) in einer Schleife veränderst, wie du Abbruchbedingungen definierst und wie du Zyklen erkennst, ohne dich zu verheddern.

 

Problemstellung

Schreibe eine Funktion, die prüft, ob eine positive ganze Zahl n eine Happy Number ist.

  • Starte mit n.
  • Berechne die Summe der Quadrate der Ziffern von n.
  • Setze n auf diese Summe und wiederhole.
  • Wenn du 1 erreichst, ist die Zahl happy.
  • Wenn sich ein Wert wiederholt, bist du in einem Zyklus und die Zahl ist nicht happy.

Mini-Beispiel (happy):

  1. 19 → 1^2 + 9^2 = 82
  2. 82 → 8^2 + 2^2 = 68
  3. 68 → 6^2 + 8^2 = 100
  4. 100 → 1^2 + 0^2 + 0^2 = 1 (happy)

 

Die Idee dahinter

Du hast einen Zustand (die aktuelle Zahl current). In jeder Runde der Schleife erzeugst du einen neuen Zustand, indem du current durch sumOfDigitSquares(current) ersetzt.

Das Problem ist nicht die Rechnung, sondern das Stoppen:

  • Stoppe sofort, wenn current == 1.
  • Stoppe auch, wenn du einen Wert schon einmal hattest (Zyklus).

Kurze Visualisierung als Zustandsliste (nicht happy, typisch):

  • 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 ... (Zyklus)

 

Schritt für Schritt zur Lösung

  1. Hilfsmethode planen: Schreibe sumOfDigitSquares(int n), die Ziffern mit % 10 und / 10 verarbeitet.
  2. Startzustand setzen: Lege current = n fest.
  3. Abbruchbedingung 1: Wenn current == 1, gib true zurück.
  4. Zyklus-Erkennung: Merke dir alle bereits gesehenen Werte (z.B. in einem Set) oder nutze einen Zeiger-Trick.
  5. Iteration: Setze current = sumOfDigitSquares(current) und gehe zur nächsten Runde.
  6. Abbruchbedingung 2: Wenn der Wert schon bekannt ist (oder sich Zeiger treffen), gib false zurück.

 

Java-Implementierung (Variante A: straightforward)

import java.util.HashSet; import java.util.Set;

public class HappyNumbersStraightforward {

public static void main(String[] args) {
    System.out.println("19 -> " + isHappy(19));
    System.out.println("2  -> " + isHappy(2));
    System.out.println("7  -> " + isHappy(7));
}

public static boolean isHappy(int n) {
    if (n <= 0) {
        return false;
    }

    Set<Integer> seen = new HashSet<>();
    int current = n;

    while (current != 1) {
        if (seen.contains(current)) {
            return false;
        }
        seen.add(current);
        current = sumOfDigitSquares(current);
    }

    return true;
}

private static int sumOfDigitSquares(int n) {
    int sum = 0;
    int value = n;

    while (value > 0) {
        int digit = value % 10;
        sum += digit * digit;
        value /= 10;
    }

    return sum;
}

}

Diese Variante ist bewusst direkt: Ein Set speichert alle Zustandswerte, die schon vorkamen. Sobald ein Wert erneut auftaucht, bist du sicher in einem Zyklus und brichst ab. Die Zustandsveränderung passiert klar sichtbar in der Zeile current = sumOfDigitSquares(current).

Vorteil: sehr leicht zu verstehen und zu debuggen. Nachteil: zusätzlicher Speicher für das Set, auch wenn er hier in der Praxis klein bleibt.

 

Java-Implementierung (Variante B: Alternative oder Verbesserung)

public class HappyNumbersTwoPointers {
public static void main(String[] args) {
    System.out.println("19 -> " + isHappy(19));
    System.out.println("2  -> " + isHappy(2));
    System.out.println("7  -> " + isHappy(7));
}

public static boolean isHappy(int n) {
    if (n <= 0) {
        return false;
    }

    int slow = n;
    int fast = n;

    do {
        slow = sumOfDigitSquares(slow);
        fast = sumOfDigitSquares(sumOfDigitSquares(fast));
    } while (slow != fast);

    return slow == 1;
}

private static int sumOfDigitSquares(int n) {
    int sum = 0;
    int value = n;

    while (value > 0) {
        int digit = value % 10;
        sum += digit * digit;
        value /= 10;
    }

    return sum;
}

}

Hier nutzt du den „Two Pointers“-Ansatz (auch bekannt aus Zyklus-Erkennung): slow geht Schritt für Schritt, fast geht doppelt so schnell. Wenn es einen Zyklus gibt, treffen sie sich irgendwann. Wenn die Zahl happy ist, endet alles bei 1, und auch dort treffen sie sich.

Vorteil: kein Set, also weniger Speicher. Nachteil: gedanklich etwas ungewohnter, aber sehr sauber, wenn du Zyklen ohne Zusatzspeicher erkennen willst.

 

Beispiel: Eingabe und Ausgabe

  • Eingabe: 19 Output: true
  • Eingabe: 2 Output: false
  • Eingabe: 7 Output: true

 

Typische Fehler

  • Falsche Abbruchbedingung: Nur auf current == 1 zu pruefen und Zyklus-Erkennung zu vergessen führt zu Endlosschleifen (z.B. bei 2).
  • Set an falscher Stelle: Den Wert erst nach dem Update in das Set zu legen, kann dazu führen, dass du Wiederholungen zu spät erkennst.
  • Ziffern nicht korrekt zerlegen: value /= 10 zu vergessen lässt die Schleife in sumOfDigitSquares hängen.
  • Quadrat falsch berechnen: Aus Versehen sum += digit * 2 statt digit * digit (kommt häufiger vor als man denkt).
  • 0 oder negative Eingaben: Das Problem ist normalerweise für positive Zahlen definiert. Ohne Check kann das Verhalten uneindeutig werden.
  • Verwechslung von Zustand und Hilfsvariable: Wenn du current und value durcheinander bringst, veränderst du aus Versehen die falsche Variable.

 

Fazit

Happy Numbers sind ein überschaubares Problem, mit dem du sehr gut Iteration, Zustandsveränderung und saubere Abbruchbedingungen trainierst. Du hast gesehen, wie man eine Rechnung in eine kleine Hilfsmethode kapselt und wie man Endlosschleifen verhindert.