Last Updated: 5 Mar, 2021
NINJA JASOOS
Easy
Asked in companies
Ninja grew 19 years older and started his own detective company. One day a kidnapper challenges our Ninja to solve a case. Kidnapper makes many duplicates of a child and each child (or we can say duplicate and the original one) is assigned a unique number. A bomb is tied to each child and it will blast within 5 minutes.
Now he gives a number ‘N’ to Ninja and tells him that the child mentioned with “Nth” Fibonacci number is the original child.
So help our Ninja in finding the “Nth” Fibonacci number so he can save the lives of children as within 5 minutes he can't defuse all the bombs alone.
Nth term of Fibonacci series F(N) is calculated using the following formula -
F(N) = F(N-1) + F(N-2),
Where, F(1) = 1 F(2) = 1
Input Format :
The first line of input contains the ‘T’ number of test cases.
The first line of each test case contains a real number ‘N’.
Output Format :
For each test case, return its equivalent Fibonacci number.
Note:
You are not required to print anything explicitly. It has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 10000
1 <= N <= 40
Time Limit: 1 second
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 NINJA_JASOOS(N-1) + NINJA_JASOOS(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