Nth Fibonacci Number

Easy

0/40

537 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains an integer ‘n’.

Output Format :

Print the n-th Fibonacci number.

Sample Input 1:

Sample Output 1:

Explanation of sample input 1 :

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.

Expected time complexity :

The expected time complexity is O(n).

Constraints:

1 <= 'n' <= 10000     
Where ‘n’ represents the number for which we have to find its equivalent Fibonacci number.

Time Limit: 1 second

Hint 1

Hint 2

Hint 3

What is recursion?

Approaches (3)

Approach 1

Approach 2

Approach 3

Recursive Approach

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.

Time Complexity

O(2^N), where ‘N’ is the number for which we are finding its equivalent Fibonacci.

As our function will be called exponentially.

Space Complexity

O(N), where ‘N’ is the given number.

As recursion uses a stack of size ‘N’

(75% EXP penalty)

(100% EXP penalty)

Nth Fibonacci Number

Console