आसान 0 हल किए गए 0% स्वीकृति

First Fibonacci With N Digits

Find the position of the first Fibonacci number that has n digits.

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

  • Add two digit arrays
  • Generate Fibonacci terms without overflow
  • Stop at the first term that meets a condition

समस्या

अनुवाद दिखाएँ

The Fibonacci sequence starts F(1) = 1, F(2) = 1, and each next term is the sum of the two before it: 1, 1, 2, 3, 5, 8, 13, 21, ... Find where the sequence first reaches n decimal digits. The terms soon outgrow 64-bit integers, so add them as digit arrays if your language has no big integers.

Implement fibonacci_with_n_digits(n).

Input

n: The number of digits.

Output

Return the index i of the first term F(i) with at least n digits. For n = 1 the answer is 1.

सीमाएँ

1 ≤ n ≤ 1000

उदाहरण

उदाहरण 1
इनपुट:
n = 2

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

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

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

व्याख्या

F(6) = 8 has one digit and F(7) = 13 has two, so the answer is 7.

उदाहरण 2
इनपुट:
n = 4

अपेक्षित आउटपुट:
expected = 17
इनपुट:
long long n = 4;

अपेक्षित आउटपुट:
long long expected = 17;
इनपुट:
long n = 4;

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

व्याख्या

F(16) = 987 and F(17) = 1597, so the answer is 17.

कैसे हल करें

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

संकेत 1

Keep only the last two terms.

संकेत 2

Store each term as digits and add them with carries.

संकेत 3

Count the index as you go, starting from F(1) = 1.

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

O(n²) time, O(n) extra space

संदर्भ

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

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

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

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

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

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