सभी चुनौतियाँ
कठिन 0 हल किए गए 0% स्वीकृति

सबसे लंबा आवर्ती दशमलव चक्र

किसी सीमा तक वह d खोजिए जिसके भिन्न 1/d में बार-बार आने वाला दशमलव खंड सबसे लंबा हो।

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

  • शेषफलों की मदद से लंबे भाग का simulation करना
  • Lookup table से दोहराव पहचानना
  • पहली बार दिखने के स्थानों से चक्र की लंबाई निकालना

समस्या

कुछ इकाई भिन्न (unit fractions) कुछ अंकों के बाद ख़त्म हो जाते हैं (1/4 = 0.25) और बाकी हमेशा दोहराते रहते हैं: 1/6 = 0.1666... में 1 अंक का खंड दोहराता है और 1/7 = 0.142857142857... में 6 अंकों का। d = 2, 3, ..., limit में से वह d खोजिए जिसके 1/d का दोहराया जाने वाला खंड सबसे लंबा हो। code में वैसे ही भाग (long division) कीजिए जैसे कागज़ पर करते हैं: जैसे ही कोई शेषफल दोबारा आता है, अंक दोहराने लगते हैं।

longest_recurring_cycle(limit) लिखिए।

इनपुट

limit: आज़माया जाने वाला सबसे बड़ा हर (denominator)।

आउटपुट

सबसे लंबे दोहराए जाने वाले खंड वाला d लौटाइए। ख़त्म हो जाने वाले भिन्न के खंड की लंबाई 0 मानी जाती है। अगर कई d बराबरी पर हों तो सबसे छोटा लौटाइए।

सीमाएँ

2 ≤ limit ≤ 2000

उदाहरण

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

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

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

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

व्याख्या

2 से 8 तक खंड की लंबाइयाँ 0, 1, 0, 0, 1, 6, 0 हैं, इसलिए उत्तर 7 है।

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

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

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

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

व्याख्या

1/3 में एक अंक दोहराता है, जबकि 1/2, 1/4 और 1/5 ख़त्म हो जाते हैं, इसलिए उत्तर 3 है।

कैसे हल करें

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

संकेत 1

1/d का हर नया अंक शेषफल को 10 से गुणा करने पर मिलता है।

संकेत 2

याद रखिए कि हर शेषफल पहली बार किस कदम पर आया था।

संकेत 3

अगर शेषफल 0 हो जाए तो दशमलव ख़त्म हो जाता है; वरना चक्र की लंबाई एक ही शेषफल के दो बार आने के बीच का अंतर है।

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

समय O(limit²), अतिरिक्त स्थान O(limit)

संदर्भ

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

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

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

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

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

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