Fibonacci Number · Coding Interview Practice

Fibonacci NumberGiven n, return the nth Fibonacci number, where F(0) = 0, F(1) = 1 and F(n) = F(n - 1) + F(n - 2).Constraints

0 <= n <= 30

Avoid the exponential recursion

O(1) extra space is possible

Examples

Input: n = 2 Output: 1

Input: n = 4 Output: 3

LetsDiscuss

Loading your session…