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

सबसे लंबी कोलाट्ज़ श्रृंखला

किसी सीमा तक वह आरंभिक संख्या खोजिए जिसकी कोलाट्ज़ श्रृंखला सबसे लंबी हो।

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

  • कोलाट्ज़ श्रृंखला बनाना
  • दोहराए काम से बचने के लिए परिणाम cache करना
  • बराबरी होने पर सबसे छोटा मान चुनना

समस्या

किसी भी धनात्मक n से शुरू करने पर कोलाट्ज़ नियम कहता है कि अगर n सम है तो अगला पद n / 2 होगा और विषम है तो 3n + 1, और श्रृंखला 1 पर पहुँचकर रुक जाती है। 6 की श्रृंखला है 6, 3, 10, 5, 16, 8, 4, 2, 1, यानी नौ पद। 1 से limit तक की सभी आरंभिक संख्याओं में से वह खोजिए जिसकी श्रृंखला में सबसे ज़्यादा पद हों।

longest_collatz_chain(limit) लिखिए।

अलग-अलग श्रृंखलाओं के आख़िरी हिस्से एक जैसे होते हैं, इसलिए हर संख्या के लिए निकाली गई लंबाई याद रखने से बहुत काम बचता है। बीच में आने वाले पद limit से बड़े हो सकते हैं; 64-bit पूर्णांक इस्तेमाल कीजिए।

इनपुट

limit: आज़माई जाने वाली सबसे बड़ी आरंभिक संख्या।

आउटपुट

वह आरंभिक संख्या लौटाइए जिसकी श्रृंखला में सबसे ज़्यादा पद हों (शुरुआती संख्या और आख़िरी 1, दोनों गिनकर)। अगर कई संख्याएँ बराबरी पर हों तो उनमें से सबसे छोटी लौटाइए।

सीमाएँ

1 ≤ limit ≤ 100,000

उदाहरण

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

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

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

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

व्याख्या

1 से 6 तक की श्रृंखलाओं में क्रमशः 1, 2, 8, 3, 6 और 9 पद हैं, इसलिए उत्तर 6 है।

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

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

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

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

व्याख्या

9 से 20 पद मिलते हैं (9, 28, 14, 7, ...), जो 10 तक की किसी भी दूसरी शुरुआत से ज़्यादा है, इसलिए उत्तर 9 है।

कैसे हल करें

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

संकेत 1

पहले एक श्रृंखला के पद गिनिए, शुरुआती संख्या और 1 को मिलाकर।

संकेत 2

जब श्रृंखला किसी ऐसी संख्या पर पहुँचे जिसकी लंबाई पहले से पता है, तो आगे बढ़ने के बजाय वह लंबाई जोड़ दीजिए।

संकेत 3

सबसे अच्छी शुरुआत को तभी बदलिए जब नई लंबाई सख़्ती से बड़ी हो।

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

समय O(limit × average new steps) (हर संख्या के लिए औसतन नए कदम), अतिरिक्त स्थान O(limit)

संदर्भ

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

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

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

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

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

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