Statement

Fibonacci numbers are a sequence of numbers where each number is the sum of the two preceding numbers. Your task is to find the nthn^{th} Fibonacci number.

The Fibonacci sequence is defined as:

F0=0, F1=1, Fn=Fn1+Fn2, F_0 = 0,\space F_1 = 1,\space F_n = F_{n-1} + F_{n-2},\space for nn \geq 2

Let’s say you have to find the fifth Fibonacci number in the sequence. From the sequence defined above, we know that F0=0F_0 = 0 and F1=1F_1 = 1. So, the sequence will be:

0,1,1,2,3,50, 1, 1, 2, 3, 5

Now, the fifth term will be 5.

Constraints:

  • 00 \leq n 900\leq 900

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.