Problem
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).
Constraints
0 ≤ n ≤ 90
Examples
Input:
n = 6
Expected output:
expected = 18
Input:
long long n = 6;
Expected output:
long long expected = 18;
Input:
long n = 6;
Expected output:
long expected = 18;
Explanation
The terms are 2, 1, 3, 4, 7, 11, 18, so L(6) = 18.
Input:
n = 0
Expected output:
expected = 2
Input:
long long n = 0;
Expected output:
long long expected = 2;
Input:
long n = 0;
Expected output:
long expected = 2;
Explanation
The sequence starts with L(0) = 2.
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
Keep the current and next terms in two variables.
Hint 2
The only difference from Fibonacci is the start: 2 and 1.
Hint 3
For n = 90 the next term would not fit in 64 bits, so stop the loop at n.
Expected complexity
O(n) time, O(1) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.