Problem

Submissions

Hints & solutions

Discuss

NINJA JASOOS

Easy

0/40

Average time to solve is 15m

Contributed by

5 upvotes

Asked in companies

Problem statement

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

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

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

Sample Input 1:

2
4
6

Sample Output 1:

3
8

Explanation of Sample Input 1:

Test Case 1:

In the first line, there is the number of test cases i.e., 2, and in the next line ‘4’is the number for which we have to find its equivalent Fibonacci number or we can say return the “4th” Fibonacci number.
So by using the property of the Fibonacci series i.e 

[ 1, 1, 2, 3]
So the “4th” element is “3” hence we get the output.

Test Case 2:

Now the number is ‘6’ so we have to find the “6th” Fibonacci number
So by using the property of the Fibonacci series i.e 

[ 1, 1, 2, 3, 5, 8]
So the “6th” element is “8” hence we get the output.

Sample Input 2 :

2
5
3

Sample Output 2 :

5
2

Hint 1

Hint 2

Hint 3

Can we use recursion to solve the problem?

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 NINJA_JASOOS(N-1) + NINJA_JASOOS(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’

(100% EXP penalty)

NINJA JASOOS

Console