Happy Number

Q: Warum erreicht der Prozess immer 1 oder eine Schleife?

Eine Zahl mit d Ziffern wird auf höchstens 81 × d abgebildet, daher schrumpfen große Zahlen schnell: Jede Startzahl bis zu 2^31-1 fällt nach einem Schritt unter 1000, und eine Zahl unter 1000 wird auf höchstens 243 abgebildet. Der Verlauf ist auf weniger als 1000 Werte beschränkt, also muss sich einer wiederholen, und von da an bildet sich ein Zyklus. 1 ist die einzige Zahl, die auf sich selbst abgebildet wird.

Q: Wie hoch ist die Zeitkomplexität der Happy-Number-Funktion?

Der erste Schritt liest die O(log n) Ziffern von n . Jeder spätere Wert ist kleiner als 1000, und der Ablauf wiederholt sich nach höchstens 20 Zahlen. Daher beträgt die Gesamtzeit O(log n) . Die Version mit Hash-Set speichert die besuchten Zahlen; Floyds Version benötigt O(1) Speicherplatz.

LeichtSchneller und langsamer Zeiger Hashing

+10

Beginne mit einer positiven ganzen Zahl n und ersetze sie immer wieder durch die Summe der Quadrate ihrer Ziffern. Zum Beispiel wird aus 12: 1² + 2² = 5. Wenn dieser Vorgang 1 erreicht, ist n eine Glückszahl; andernfalls kreist er endlos durch Zahlen, in denen 1 nie vorkommt. Gib true zurück, wenn n eine Glückszahl ist, und false, wenn nicht.

Funktion

isHappy(n: integer) → boolean

ninteger: die zu testende positive ganze Zahl
Gibt zurückboolean: wahr, wenn die wiederholte Summe der Ziffernquadrate 1 erreicht, falsch, wenn sie sich endlos wiederholt

Einschränkungen

1 ≤ n ≤ 2³¹-1

Beispiele

Eingabe: n = 7
Ausgabe: true
Erklärung: 7 wird zu 49, dann 4² + 9² = 97, dann 130, dann 10 und dann 1. Der Prozess erreicht 1, also ist 7 eine Glückszahl.

Eingabe: n = 2
Ausgabe: false
Erklärung: Aus 2 werden 4, 16, 37, 58, 89, 145, 42, 20 und dann wieder 4. Von dort an wiederholen sich dieselben acht Zahlen für immer und erreichen nie 1.

Eingabe: n = 100
Ausgabe: true
Erklärung: 1² + 0² + 0² = 1, daher erreicht 100 nach einem Schritt 1.

+16 versteckte Tests beim Einreichen

Weiterführende Frage

Wie würdest du schnell die Glückszahlen von 1 bis 10^6 zählen und dabei die Ergebnisse für Zahlen unter 1000 wiederverwenden, anstatt jeden Startwert von Grund auf durchzugehen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Der Ablauf kann niemals ins Unendliche laufen. Eine Zahl mit 10 Ziffern wird auf höchstens 10 × 81 = 810 abgebildet, und eine Zahl unter 1000 auf höchstens 3 × 81 = 243. Daher bleibt der Ablauf nach einem Schritt unter weniger als 1000 Werten und muss 1 erreichen oder eine Zahl wiederholen. Damit wird das Problem zur Zyklenerkennung: Merke dir, was du bereits gesehen hast, oder lass einen langsamen und einen schnellen Läufer laufen und prüfe, ob sie sich treffen.

Erinnere dich an jede Zahl, die du gesehen hast

Idee

Durchlaufe die Folge und speichere jede Zahl in einer Hashtabelle. Bevor du von einer Zahl zur nächsten gehst, prüfe, ob sie bereits in der Hashtabelle enthalten ist. Für 2 füllt sich die Hashtabelle mit 2, 4, 16, 37, 58, 89, 145, 42 und 20, und der nächste Wert ist 4, der bereits enthalten ist: Der Durchlauf hat einen Zyklus geschlossen, ohne 1 zu erreichen, also ist 2 keine Glückszahl. Bei 1 endet der Durchlauf mit true.

Das ist korrekt, weil die nächste Zahl nur von der aktuellen abhängt. Sobald eine Zahl erneut auftritt, wiederholt sich alles danach exakt, sodass keine neue Zahl auftreten kann und 1 niemals erreicht wird.

Der Durchlauf ist kurz. Der erste Schritt verarbeitet die O(log n) Ziffern von n, und jeder spätere Wert ist kleiner als 1000. Kein Durchlauf besucht mehr als 20 verschiedene Zahlen, bevor er 1 erreicht oder sich wiederholt. Die Hashtabelle speichert diese Zahlen. Der C-Code verwendet ein Flag-Array mit 1000 Einträgen als Hashtabelle und beginnt mit dem Speichern nach dem ersten Schritt, wenn jeder Wert kleiner als 1000 ist.

Algorithmus

Erstelle eine leere Hash-Menge seen.
Solange n nicht 1 ist, gib false zurück, wenn n in seen enthalten ist.
Füge andernfalls n zu seen hinzu und ersetze n durch die Summe der Quadrate seiner Ziffern.
Wenn die Schleife endet, ist n 1: Gib true zurück.

def digitSquareSum(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total


def isHappy(n):
    seen = set()
    while n != 1:
        if n in seen:
            return False  # back at an earlier number: a loop without 1
        seen.add(n)
        n = digitSquareSum(n)
    return True

Schnelle und langsame Läufer (Floyds Zyklenerkennung)

Idee

Stell dir jede Zahl als Knoten mit einem Pfeil vor, der auf ihre Ziffernquadratsumme zeigt. Wenn du den Pfeilen von n aus folgst, erreichst du entweder 1, deren Pfeil zurück auf 1 zeigt, oder du gerätst in eine Schleife. Das entspricht der Struktur einer verketteten Liste, die einen Zyklus enthalten kann, und Floyds Algorithmus erkennt einen Zyklus, ohne etwas zu speichern: slow macht pro Runde einen Schritt und fast zwei.

Enthält die Schleife nicht die 1, kreisen beide Läufer darin, und in jeder Runde gewinnt fast einen Schritt gegenüber slow, sodass sich der Abstand um eins verringert, bis sie bei derselben Zahl stehen. Bei 2 treffen sie sich nach sieben Runden bei 42. Erreicht der Lauf die 1, kommt fast zuerst dort an und bleibt dort, denn die Summe für 1 ist 1. Halte also an, wenn fast 1 ist oder die Läufer sich treffen, und gib zurück, ob fast 1 ist.

Bei 7 bewegt sich slow über 7, 49, 97, während sich fast über 49, 130, 1 bewegt, und die Schleife endet mit fast auf 1. Die Anzahl der Runden beträgt höchstens ein kleines Vielfaches der Länge des Laufs, sodass die Laufzeit der Variante mit einer Menge entspricht; der Speicherbedarf beträgt zwei Ganzzahlen.

Algorithmus

Schreibe eine Hilfsfunktion, die die Summe der Quadrate der Ziffern einer Zahl zurückgibt.
Setze slow = n und setze fast auf die Zahl, die einen Schritt nach n kommt.
Solange fast nicht 1 ist und slow sich von fast unterscheidet, bewege slow einen Schritt und fast zwei Schritte.
Gib zurück, ob fast 1 ist.

def digitSquareSum(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total


def isHappy(n):
    slow = n
    fast = digitSquareSum(n)
    # fast moves two steps for every step of slow; they meet only inside a loop.
    while fast != 1 and slow != fast:
        slow = digitSquareSum(slow)
        fast = digitSquareSum(digitSquareSum(fast))
    return fast == 1

Stolperfallen und Grenzfälle

Die Ziffernarithmetik ist kurz. Die meisten Fehler entstehen dadurch, wann die Schleife endet.

Die Schleife läuft bis zum Wert 1, ohne eine weitere Abbruchbedingung. Bei 2 endet diese Schleife nie.
slow und fast starten mit derselben Zahl, und slow != fast wird vor dem ersten Schritt geprüft. Die Schleife wird nie ausgeführt, und 7 wird als unglücklich eingestuft. Starte fast einen Schritt voraus oder bewege beide vor dem ersten Vergleich.
In der Floyd-Variante wird slow == 1 zurückgegeben. fast erreicht zuerst 1 und die Schleife endet sofort, während slow noch bei 97 sein kann.
Die Ziffern werden addiert, statt ihre Quadrate zu addieren, oder die ganze Zahl wird quadriert. Für 12 ist der nächste Wert 1² + 2² = 5, nicht 3 und nicht 144.
n wird immer dann als unglücklich eingestuft, wenn sich die Läufer treffen. 1 wird auf sich selbst abgebildet, daher treffen sich die Läufer auch bei 1; prüfe, wo sie sich getroffen haben, oder brich ab, sobald fast 1 ist.

Häufige Fragen4

Warum erreicht der Prozess immer 1 oder eine Schleife?

Eine Zahl mit d Ziffern wird auf höchstens 81 × d abgebildet, daher schrumpfen große Zahlen schnell: Jede Startzahl bis zu 2^31-1 fällt nach einem Schritt unter 1000, und eine Zahl unter 1000 wird auf höchstens 243 abgebildet. Der Verlauf ist auf weniger als 1000 Werte beschränkt, also muss sich einer wiederholen, und von da an bildet sich ein Zyklus. 1 ist die einzige Zahl, die auf sich selbst abgebildet wird.

Wie hoch ist die Zeitkomplexität der Happy-Number-Funktion?

Der erste Schritt liest die O(log n) Ziffern von n. Jeder spätere Wert ist kleiner als 1000, und der Ablauf wiederholt sich nach höchstens 20 Zahlen. Daher beträgt die Gesamtzeit O(log n). Die Version mit Hash-Set speichert die besuchten Zahlen; Floyds Version benötigt O(1) Speicherplatz.

Warum enden alle unglücklichen Zahlen bei 4?

Die Überprüfung jeder Zahl unter 1000 zeigt genau eine Schleife, die 1 vermeidet: 4, 16, 37, 58, 89, 145, 42, 20 und zurück zu 4. Da jeder Startwert unter 1000 fällt, landet jede nicht glückliche Zahl in dieser Schleife. Eine Lösung kann anhalten, sobald sie auf 4 trifft, aber das beruht auf einer Tatsache, die du in einem Vorstellungsgespräch begründen müsstest; die Menge und Floyds Methode benötigen keine solchen Kenntnisse.

Wie hängt die Glückszahl mit dem Zyklus in einer verketteten Liste zusammen?

Beide fragen, ob man durch das Folgen eines Pfeils von jedem Element aus irgendwann zu einem bereits besuchten Element zurückkehrt. Bei einer glücklichen Zahl ist der Pfeil die Summe der Quadrate der Ziffern; bei einer verketteten Liste ist es der Zeiger auf das nächste Element. Deshalb lösen Floyds schnelle und langsame Läufer beide Probleme mit konstantem Speicherbedarf.

Python

def isHappy(n):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

n = 7

Erwartet

true