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.
Die Kaprekar-Konstante 6174 ist ein bekanntes Zahlenphänomen: Nimm eine vierstellige Zahl, sortiere ihre Ziffern absteigend und aufsteigend, bilde die Differenz, und wiederhole das Ganze. Fast immer landest du nach wenigen Runden bei 6174.
Das Problem ist beliebt, weil es simpel wirkt, aber viele Grundlagen trainiert: Ziffernmanipulation, saubere Iteration, und eine gute Abbruchbedingung.
In diesem Artikel baust du eine kleine Java-Lösung (Java 17+), siehst typische Fehler, und bekommst direkt Beispiele, die du auf der Konsole testen kannst.
Problemstellung
Gegeben ist eine Zahl n mit genau vier Ziffern (inklusive führender Nullen, also z.B. 0001 ist erlaubt). Führe wiederholt folgende Schritte aus, bis du 6174 erreichst oder feststellst, dass du in einem anderen Fixpunkt landest:
- Zerlege
nin vier Ziffern. - Sortiere die Ziffern absteigend zu einer Zahl
desc. - Sortiere die Ziffern aufsteigend zu einer Zahl
asc. - Berechne
n = desc - asc. - Zähle die Schritte.
Wichtige Regeln/Constraints:
- Führende Nullen sind Teil der vierstelligen Darstellung (z.B.
100wird als0100behandelt). - Wenn alle Ziffern gleich sind (z.B.
1111), kommst du bei0000raus und bleibst dort. - Du solltest eine maximale Schrittzahl setzen (z.B. 20), um Endlosschleifen bei falscher Logik zu vermeiden.
Mini-Beispiel (Start: 3524):
- Ziffern: 3, 5, 2, 4
desc = 5432,asc = 2345n = 5432 - 2345 = 3087- Wiederholen bis
6174
Die Idee dahinter
Du machst immer wieder dasselbe: Ziffern extrahieren, neu anordnen, Differenz bilden. Das ist ein klassischer Fall für Iteration: Ein Zustand (n) wird Schritt für Schritt aktualisiert.
Die Kaprekar-Konstante 6174 ist dabei ein stabiler Zielzustand: Wenn du dort angekommen bist, bleibt es dabei, denn 7641 - 1467 = 6174.
Kurze Visualisierung als Liste:
- Eingabe: vier Ziffern
- Transformation: sortiere zu
descundasc - Update:
n = desc - asc - Abbruch:
n == 6174odern == 0(oder Schrittlimit erreicht)
Schritt für Schritt zur Lösung
- Validiere die Eingabe: liegt
nzwischen0und9999? - Formatiere die Zahl immer als vier Stellen, z.B. mit
String.format("%04d", n). - Extrahiere die vier Ziffern in ein Array.
- Sortiere die Ziffern aufsteigend (und nutze sie auch für absteigend, nur rückwärts gelesen).
- Baue aus den sortierten Ziffern die Zahlen
ascunddesc. - Berechne
n = desc - ascund erhöhe den Zähler. - Brich ab, wenn
n == 6174, oder wennn == 0, oder wenn ein Schrittlimit erreicht ist.
Java-Implementierung (Variante A: straightforward)
import java.util.Arrays;
public class KaprekarStraightforward {
private static final int TARGET = 6174;
private static final int MAX_STEPS = 20;
public static void main(String[] args) {
runDemo(3524);
runDemo(100);
runDemo(1111);
}
private static void runDemo(int start) {
System.out.println("Start: " + format4(start));
int n = start;
for (int step = 1; step <= MAX_STEPS; step++) {
int[] digits = toDigits4(n);
Arrays.sort(digits);
int asc = fromDigitsAsc(digits);
int desc = fromDigitsDesc(digits);
int next = desc - asc;
System.out.println(step + ": desc=" + format4(desc)
+ " asc=" + format4(asc)
+ " next=" + format4(next));
n = next;
if (n == TARGET) {
System.out.println("Reached " + TARGET + " in " + step + " steps.");
System.out.println();
return;
}
if (n == 0) {
System.out.println("Reached 0000 (all digits equal case).");
System.out.println();
return;
}
}
System.out.println("Stopped after " + MAX_STEPS + " steps (safety limit).");
System.out.println();
}
private static int[] toDigits4(int n) {
if (n < 0 || n > 9999) {
throw new IllegalArgumentException("n must be in range 0..9999");
}
String s = format4(n);
int[] digits = new int[4];
for (int i = 0; i < 4; i++) {
digits[i] = s.charAt(i) - '0';
}
return digits;
}
private static int fromDigitsAsc(int[] sortedAsc) {
int value = 0;
for (int d : sortedAsc) {
value = value * 10 + d;
}
return value;
}
private static int fromDigitsDesc(int[] sortedAsc) {
int value = 0;
for (int i = sortedAsc.length - 1; i >= 0; i--) {
value = value * 10 + sortedAsc[i];
}
return value;
}
private static String format4(int n) {
return String.format("%04d", n);
}
}Diese Variante ist bewusst direkt: Du siehst jede Phase (Ziffern holen, sortieren, Zahlen bauen, Differenz). Praktisch ist format4, weil du so führende Nullen in Ausgabe und Verarbeitung konsistent behandelst. Das Schrittlimit MAX_STEPS ist ein Sicherheitsnetz, falls du später mal etwas umbauen und dabei eine Abbruchbedingung vergessen solltest.
Java-Implementierung (Variante B: Alternative oder Verbesserung)
public class KaprekarAlternative {
private static final int TARGET = 6174;
public static void main(String[] args) {
printResult(3524);
printResult(100);
printResult(2111);
}
private static void printResult(int start) {
Result r = stepsToKaprekar(start);
System.out.println("Start: " + format4(start)
+ " - steps=" + r.steps()
+ " - end=" + format4(r.endValue()));
}
public static Result stepsToKaprekar(int start) {
validateRange(start);
int n = start;
int steps = 0;
while (n != TARGET && n != 0) {
StepNumbers sn = computeAscDesc(n);
n = sn.desc() - sn.asc();
steps++;
}
return new Result(steps, n);
}
private static StepNumbers computeAscDesc(int n) {
int[] count = digitCount4(n);
int asc = buildFromCountAsc(count);
int desc = buildFromCountDesc(count);
return new StepNumbers(asc, desc);
}
private static int[] digitCount4(int n) {
String s = format4(n);
int[] count = new int[10];
for (int i = 0; i < 4; i++) {
int d = s.charAt(i) - '0';
count[d]++;
}
return count;
}
private static int buildFromCountAsc(int[] count) {
int value = 0;
for (int d = 0; d <= 9; d++) {
for (int k = 0; k < count[d]; k++) {
value = value * 10 + d;
}
}
return value;
}
private static int buildFromCountDesc(int[] count) {
int value = 0;
for (int d = 9; d >= 0; d--) {
for (int k = 0; k < count[d]; k++) {
value = value * 10 + d;
}
}
return value;
}
private static void validateRange(int n) {
if (n < 0 || n > 9999) {
throw new IllegalArgumentException("n must be in range 0..9999");
}
}
private static String format4(int n) {
return String.format("%04d", n);
}
public record StepNumbers(int asc, int desc) { }
public record Result(int steps, int endValue) { }
}Hier ist die Iteration bewusst als Methode stepsToKaprekar gekapselt, die einen klaren Rückgabewert liefert. Statt ein Array zu sortieren, zählt die Variante die Ziffern in digitCount4 und baut daraus asc und desc. Das ist oft gut lesbar und vermeidet Sortierlogik; für vier Ziffern ist beides schnell, aber die Zähllogik ist eine saubere Alternative.
Beispiel: Eingabe und Ausgabe
Beispiel 1: Start 3524 endet bei 6174 (typisch in wenigen Schritten).
Beispiel 2: Start 0100 (als Zahl 100) wird verarbeitet wie 0100 und erreicht ebenfalls 6174.
Beispiel 3: Start 1111 wird zu 0000 und bleibt dort: 1111 - 1111 = 0000.
Typische Fehler
- Führende Nullen ignoriert: Wenn du
100nicht als0100behandelst, stimmenasc/descnicht. - Falsche Abbruchbedingung: Nur auf
6174zu prüfen reicht nicht, weil0000ein Fixpunkt ist (alle Ziffern gleich). - Off-by-one beim Schrittzähler: Zähle genau dann, wenn du einen Kaprekar-Schritt wirklich ausgeführt hast.
- Aufsteigend/absteigend verwechselt: Besonders wenn du mit Strings arbeitest:
ascunddescmüssen exakt gegensinnig sein. - Ungenügende Eingabevalidierung: Werte kleiner als
0oder größer als9999sollten sauber abgelehnt werden. - Endlosschleife durch Bug: Setze ein Schrittlimit (z.B.
20) als Sicherheitsnetz bei Experimenten.
Fazit
Mit der Kaprekar-Konstante (6174) übst du sehr konkrete Basics: Ziffern sauber behandeln, Iterationen stabil aufbauen und Abbruchbedingungen richtig setzen. Du hast zwei Java-Varianten gesehen: einmal straightforward mit Sortieren und einmal als Alternative über Ziffernzählung.
