Problem
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).
Constraints
0 ≤ n ≤ 90
Examples
Example 1
Input:
n = 10
Expected output:
expected = 55Input:
long long n = 10;
Expected output:
long long expected = 55;Input:
long n = 10;
Expected output:
long expected = 55;Explanation
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55: F(10) = 55.
Example 2
Input:
n = 0
Expected output:
expected = 0Input:
long long n = 0;
Expected output:
long long expected = 0;Input:
long n = 0;
Expected output:
long expected = 0;Explanation
By definition F(0) = 0.
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
The first two values are fixed, so start from the base cases.
Hint 2
Build later values from the two previous ones instead of recomputing recursively.
Hint 3
Use an iterative approach to avoid repeated work and deep recursion.
Expected complexity
O(n) time, O(1) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.