समस्या
The Lucas numbers follow the same rule as the Fibonacci numbers, each term being the sum of the two before it, but they start differently: L(0) = 2 and L(1) = 1. The sequence goes 2, 1, 3, 4, 7, 11, 18, 29, …
Implement lucas_numbers(n).
Input
n: The index of the term, starting at 0.
Output
Return L(n).
सीमाएँ
0 ≤ n ≤ 90
उदाहरण
इनपुट:
n = 6
अपेक्षित आउटपुट:
expected = 18
इनपुट:
long long n = 6;
अपेक्षित आउटपुट:
long long expected = 18;
इनपुट:
long n = 6;
अपेक्षित आउटपुट:
long expected = 18;
व्याख्या
The terms are 2, 1, 3, 4, 7, 11, 18, so L(6) = 18.
इनपुट:
n = 0
अपेक्षित आउटपुट:
expected = 2
इनपुट:
long long n = 0;
अपेक्षित आउटपुट:
long long expected = 2;
इनपुट:
long n = 0;
अपेक्षित आउटपुट:
long expected = 2;
व्याख्या
The sequence starts with L(0) = 2.
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Keep the current and next terms in two variables.
संकेत 2
The only difference from Fibonacci is the start: 2 and 1.
संकेत 3
For n = 90 the next term would not fit in 64 bits, so stop the loop at n.
अपेक्षित जटिलता
O(n) time, O(1) extra space
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।