Statement

Implement a function to find the nth^{th} Fibonacci number in the Fibonacci sequence.

Fibonacci numbers form a sequence known as the Fibonacci sequence, where each number is the sum of two preceding ones, starting from 00 and 11.

The Fibonacci numbers are defined as:

  • F0=0F_0= 0
  • F1=1F_1= 1
  • Fn=Fn1+Fn2F_n= F_{n-1} + F_{n-2}, for n2n \geq 2

Based on the definition above, the first 1010 Fibonacci numbers starting, from the 0th0^{th}, are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 340, \space 1, \space 1, \space 2, \space 3, \space 5, \space 8, \space 13, \space 21, \space 34.

Sample input

8

Expected output

21

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