 New update is available. Click here to update.

# N-th Fibonacci Number

Last Updated: 5 Feb, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### Since the answer can be very large, return the answer modulo 10^9 +7.

##### Fibonacci number is calculated using the following formula:
``````F(n) = F(n-1) + F(n-2),
Where, F(1) = F(2) = 1.
``````
##### For Example:
``````For ‘N’ = 5, the output will be 5.
``````
##### Input Format:
``````The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains a single integer ‘N’, representing the integer for which we have to find its equivalent Fibonacci number.
``````
##### Output Format:
``````For each test case, print a single integer representing the N’th Fibonacci number.

Return answer modulo 10^9 + 7.

Output for each test case will be printed in a separate line.
``````
##### Note:
``````You are not required to print anything; it has already been taken care of. Just implement the function.
``````
##### Constraints:
``````1 <= T <= 10
1 <= N <= 10^5

Time Limit: 1 sec.
``````
``````Can you solve it in Time Complexity better than O(N)?
`````` ## Approach 1

• 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.
SIMILAR PROBLEMS

Spiral Matrix

Posted: 24 Nov, 2022
Difficulty: Easy

Ninja And The Strictly Increasing Array

Posted: 27 Nov, 2022
Difficulty: Moderate

Maximum GCD

Posted: 8 Dec, 2022
Difficulty: Hard

Prime?

Posted: 9 Dec, 2022
Difficulty: Easy

Co-Prime

Posted: 14 Dec, 2022
Difficulty: Hard