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