Alle Herausforderungen
Schwierig 0 gelöst 0% Erfolgsquote

Longest Recurring Cycle

Find the d up to a limit whose fraction 1/d has the longest repeating decimal block.

Das lernst du

  • Simulate long division with remainders
  • Detect a repeat with a lookup table
  • Find a cycle length from first positions

Problem

Übersetzung anzeigen

Some unit fractions end (1/4 = 0.25) and the rest repeat forever: 1/6 = 0.1666... repeats a block of 1 digit and 1/7 = 0.142857142857... a block of 6. Among d = 2, 3, ..., limit, find the d whose 1/d has the longest repeating block. Do the long division by hand in code: the digits start repeating as soon as a remainder comes back.

Implement longest_recurring_cycle(limit).

Input

limit: The largest denominator to try.

Output

Return the d with the longest repeating block. A fraction that ends has a block length of 0. If several d tie, return the smallest.

Einschränkungen

2 ≤ limit ≤ 2000

Beispiele

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

Block lengths for 2 to 8 are 0, 1, 0, 0, 1, 6, 0, so the answer is 7.

Beispiel 2
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 repeats one digit, 1/2, 1/4 and 1/5 end, so the answer is 3.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Each new digit of 1/d comes from the remainder times 10.

Hinweis 2

Remember the step where each remainder first appeared.

Hinweis 3

If the remainder becomes 0 the decimal ends; otherwise the cycle length is the gap between two visits of the same remainder.

Erwartete Komplexität

O(limit²) time, O(limit) extra space

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.