समस्या
कुछ इकाई भिन्न (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
उदाहरण
इनपुट:
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 है।
इनपुट:
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 के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।