Nth Fibonacci
EasyP1Coding
Return the n-th Fibonacci number, where F(0) = 0, F(1) = 1 and F(n) = F(n-1) + F(n-2).
The naive double recursion is exponential. Write a version that runs in linear time.
Example 1
- Input
- n = 2
- Output
- 1
Example 2
- Input
- n = 5
- Output
- 5
Example 3
- Input
- n = 10
- Output
- 55
Constraints
- 0 <= n <= 40
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 9. ⌘Enter runs, ⌘⇧Enter submits.