Problem
Manche Stammbrüche brechen ab (1/4 = 0,25), die übrigen sind periodisch: 1/6 = 0,1666... hat eine Periode der Länge 1 und 1/7 = 0,142857142857... eine der Länge 6. Finde unter d = 2, 3, ..., limit das d, für das 1/d die längste Periode hat. Führe dazu die schriftliche Division im Code durch: Die Ziffern wiederholen sich, sobald ein Rest zum zweiten Mal auftritt.
Implementiere longest_recurring_cycle(limit).
Eingabe
limit: Der größte Nenner, der ausprobiert wird.
Ausgabe
Gib das d mit der längsten Periode zurück. Ein abbrechender Bruch hat die Periodenlänge 0. Bei Gleichstand gib das kleinste d zurück.
Einschränkungen
2 ≤ limit ≤ 2000
Beispiele
Eingabe:
limit = 8
Erwartete Ausgabe:
expected = 7
Eingabe:
long long limit = 8;
Erwartete Ausgabe:
long long expected = 7;
Eingabe:
long limit = 8;
Erwartete Ausgabe:
long expected = 7;
Erläuterung
Die Periodenlängen für 2 bis 8 sind 0, 1, 0, 0, 1, 6, 0, also lautet die Antwort 7.
Eingabe:
limit = 5
Erwartete Ausgabe:
expected = 3
Eingabe:
long long limit = 5;
Erwartete Ausgabe:
long long expected = 3;
Eingabe:
long limit = 5;
Erwartete Ausgabe:
long expected = 3;
Erläuterung
1/3 hat eine einstellige Periode, 1/2, 1/4 und 1/5 brechen ab, also lautet die Antwort 3.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Jede neue Ziffer von 1/d ergibt sich aus dem Rest mal 10.
Hinweis 2
Merke dir, in welchem Schritt jeder Rest zum ersten Mal aufgetreten ist.
Hinweis 3
Wird der Rest 0, bricht die Dezimalzahl ab. Sonst ist die Periodenlänge der Abstand zwischen zwei Vorkommen desselben Rests.
Erwartete Komplexität
Zeit O(limit²), zusätzlicher Speicher O(limit)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.