समस्या
फ़िबोनाची अनुक्रम F(1) = 1, F(2) = 1 से शुरू होता है, और हर अगला पद पिछले दो पदों का योग होता है: 1, 1, 2, 3, 5, 8, 13, 21, ... पता लगाइए कि अनुक्रम पहली बार कहाँ n दशमलव अंकों तक पहुँचता है। पद जल्दी ही 64-bit पूर्णांकों से बड़े हो जाते हैं, इसलिए अगर आपकी भाषा में big integers नहीं हैं तो उन्हें अंकों के arrays के रूप में जोड़िए।
fibonacci_with_n_digits(n) लिखिए।
इनपुट
n: अंकों की संख्या।
आउटपुट
उस पहले पद F(i) का index i लौटाइए जिसमें कम से कम n अंक हों। n = 1 के लिए उत्तर 1 है।
सीमाएँ
1 ≤ n ≤ 1000
उदाहरण
इनपुट:
n = 2
अपेक्षित आउटपुट:
expected = 7
इनपुट:
long long n = 2;
अपेक्षित आउटपुट:
long long expected = 7;
इनपुट:
long n = 2;
अपेक्षित आउटपुट:
long expected = 7;
व्याख्या
F(6) = 8 में एक अंक है और F(7) = 13 में दो, इसलिए उत्तर 7 है।
इनपुट:
n = 4
अपेक्षित आउटपुट:
expected = 17
इनपुट:
long long n = 4;
अपेक्षित आउटपुट:
long long expected = 17;
इनपुट:
long n = 4;
अपेक्षित आउटपुट:
long expected = 17;
व्याख्या
F(16) = 987 और F(17) = 1597, इसलिए उत्तर 17 है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
सिर्फ़ आख़िरी दो पद रखिए।
संकेत 2
हर पद को अंकों के रूप में रखिए और हासिल के साथ जोड़िए।
संकेत 3
साथ-साथ index गिनते जाइए, F(1) = 1 से शुरू करके।
अपेक्षित जटिलता
समय O(n²), अतिरिक्त स्थान O(n)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।