कठिन 0 हल किए गए 0% स्वीकृति

Longest Recurring Cycle

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

आप क्या सीखेंगे

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

समस्या

अनुवाद दिखाएँ

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.

सीमाएँ

2 ≤ limit ≤ 2000

उदाहरण

उदाहरण 1
इनपुट:
limit = 8

अपेक्षित आउटपुट:
expected = 7
इनपुट:
long long limit = 8;

अपेक्षित आउटपुट:
long long expected = 7;
इनपुट:
long limit = 8;

अपेक्षित आउटपुट:
long expected = 7;

व्याख्या

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

उदाहरण 2
इनपुट:
limit = 5

अपेक्षित आउटपुट:
expected = 3
इनपुट:
long long limit = 5;

अपेक्षित आउटपुट:
long long expected = 3;
इनपुट:
long limit = 5;

अपेक्षित आउटपुट:
long expected = 3;

व्याख्या

1/3 repeats one digit, 1/2, 1/4 and 1/5 end, so the answer is 3.

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

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

संकेत 2

Remember the step where each remainder first appeared.

संकेत 3

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

अपेक्षित जटिलता

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

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।