समस्या
The Fibonacci sequence starts 0, 1 and each next number is the sum of the previous two: 0, 1, 1, 2, 3, 5, 8, …. F(0) = 0 and F(1) = 1.
Implement fibonacci(n).
Input
n: The position in the sequence.
Output
Return F(n).
सीमाएँ
0 ≤ n ≤ 90
उदाहरण
उदाहरण 1
इनपुट:
n = 10
अपेक्षित आउटपुट:
expected = 55इनपुट:
long long n = 10;
अपेक्षित आउटपुट:
long long expected = 55;इनपुट:
long n = 10;
अपेक्षित आउटपुट:
long expected = 55;व्याख्या
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55: F(10) = 55.
उदाहरण 2
इनपुट:
n = 0
अपेक्षित आउटपुट:
expected = 0इनपुट:
long long n = 0;
अपेक्षित आउटपुट:
long long expected = 0;इनपुट:
long n = 0;
अपेक्षित आउटपुट:
long expected = 0;व्याख्या
By definition F(0) = 0.
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
The first two values are fixed, so start from the base cases.
संकेत 2
Build later values from the two previous ones instead of recomputing recursively.
संकेत 3
Use an iterative approach to avoid repeated work and deep recursion.
अपेक्षित जटिलता
O(n) time, O(1) extra space
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।