Last Updated: 19 Apr, 2017
Nth Fibonacci Number
Easy
Asked in companies
The n-th term of Fibonacci series F(n), where F(n) is a function, is calculated using the following formula -
F(n) = F(n - 1) + F(n - 2),
Where, F(1) = 1, F(2) = 1
Provided 'n' you have to find out the n-th Fibonacci Number. Handle edges cases like when 'n' = 1 or 'n' = 2 by using conditionals like if else and return what's expected.
"Indexing is start from 1"
Example :
Input: 6
Output: 8
Explanation: The number is ‘6’ so we have to find the “6th” Fibonacci number.
So by using the given formula of the Fibonacci series, we get the series:
[ 1, 1, 2, 3, 5, 8, 13, 21]
So the “6th” element is “8” hence we get the output.
Input Format :
The first line contains an integer ‘n’.
Output Format :
Print the n-th Fibonacci number.
Approaches
- In this approach, we use recursion and uses a basic condition that :
- If ‘N’ is smaller than ‘1’(N<=1) we return ‘N’
- Else we call the function again as ninjaJasoos(N-1) + ninjaJasoos(N-2).
- In this way, we reached our answer.
Ans of ‘i-th’ number is = ‘ans[i-11+ans[i-2]’, so
- With the help of dynamic programming, we try to store the previous value as the previous value leads to a solution.
- So we use an array named as ‘dp’ of size ‘N+1’ to store the value.
- On the first index of ‘dp[0]=0’ we store ‘0’ and on the first index of ‘dp[1]=1’ we store ‘1’.
- Now run a loop and iterate through the “Nth”number like ‘dp[i]=dp[i-2]+dp[i-1]’.
- dp[n] will contain the Fibonacci number of “Nth”number.
- Return ‘dp[n]’.
- We take three integers a, b, c and we initialized a=0, b=1 as now we want to optimize the space by only storing “2” last numbers as we need only them.
- Now we run a loop up to our “Nth” number and by using property the next number is the sum of two previous numbers like “c=a+b.
- Now we update “a=b” and “b=c” at every step of the iteration.
- In this way when our loop finished “b” contains the “Nth” Fibonacci number.
- Return ‘b'.
Similar problems