Skip to main content
Back to ChallengesFibonacci NumberEasy 10 min

Fibonacci Number

Given n, calculate the n-th Fibonacci number. The Fibonacci sequence is defined as F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1.

Examples

Input: n = 2
Output: 1
F(2) = F(1) + F(0) = 1 + 0 = 1.
Input: n = 4
Output: 3
F(4) = F(3) + F(2) = 2 + 1 = 3.

Constraints

  • • 0 <= n <= 30

Complexity Analysis

Time
O(n)
linear scan.
Space
O(1)
constant storage space.

Test Cases

#1 Base case F(0)
Input: 0
Expected: 0
#2 Base case F(1)
Input: 1
Expected: 1
#3 F(2)
Input: 2
Expected: 1
#4 F(4)
Input: 4
Expected: 3
#5 F(10)
Input: 10
Expected: 55
JavaScript
Output
Click "Run Code" to see output here...