Ninja And Fibonacci Numbers

Easy
0/40
Average time to solve is 15m
9 upvotes
Asked in companies
Tricon Infotech Pvt LtdFlipkart limitedRaja Software Labs (RSL)

Problem statement

Ninja has been given a number ‘SUM’. Ninja has to print the minimum number of Fibonacci numbers whose sum is equal to ‘SUM’.

As Ninja is busy at work, he assigns this task to you. Can you help Ninja to solve this task?

Note :

1. Ninja can use the same Fibonacci number any number of times.
2. It is also guaranteed that there are always some Fibonacci numbers whose sum is equal to ‘SUM’.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single integer ‘SUM’ denotes the sum of some Fibonacci numbers.
Output Format : 
For each test case, print the minimum number of Fibonacci numbers whose sum is equal to ‘SUM’.

Output for every test case will be printed in a separate line.
Note : 
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints : 
1 <= ‘T’ <= 50
1 <= ‘SUM’ <= 10000

Time limit: 1 sec
Sample Input 1 :
2
8
15
Sample Output 1 :
1
2
Explanation of sample input 1 :
As we know Fibonacci series is: 1 1 2 3 5 8 13 21 34

In the first test case, for ‘SUM’ = 8 we can use only 8.
In the second test case, for ‘SUM’ = 15 we can use only 13 + 2 = 15.
Sample Input 2 :
2
25
11
Sample Output 2 :
3
2
Explanation of sample input 2 :
As we know Fibonacci series is: 1 1 2 3 5 8 13 21 34

In the first test case, for ‘SUM’ = 25 we can use only 21 + 3 + 1 = 25.
In the second test case, for ‘SUM’ = 11 we can use only 8 + 3 = 11.
Hint

Can you think of going through recursively?

Approaches (3)
Recursion

The basic idea is we first subtract the biggest Fibonacci number ‘X’ from ‘SUM’. Then recursively find the answer for ‘SUM’ - ‘X’.

Recurrence relation is : f(‘SUM’) = f(‘SUM’ - ‘X’) + 1.

 

The steps are as follows:

 

  1. Base Case: If ‘SUM’ is less than 2 return ‘SUM’.
  2. Declare two variables ‘a’ = 1 and ‘b’ = 1.
  3. While ‘b’ <= ‘SUM’ :
    • ‘b’ = ‘b’ + a.
    • ‘a’ = ‘b’ - ‘a’.
  4. Finally, return 1 + findMinFibNums(‘SUM’ - ‘a’).
Time Complexity

O(log(‘SUM’) ^ 2), where ‘SUM’ is the sum of some Fibonacci numbers.

 

Because first, we find the greatest Fibonacci number i.e ‘X’, and then make recursive calls for ‘SUM’ - ‘X’. We know there are at most log(‘SUM’) Fibonacci numbers that are less than ‘SUM’. Hence the overall time complexity will be O(log(‘SUM’) ^ 2).

Space Complexity

O(log(‘SUM’)), where ‘SUM’ is the sum of some Fibonacci numbers.

 

Because in recursion O(log(‘SUM’)) space is used in the recursion stack. Hence the space complexity is O(log(‘SUM’)).

Code Solution
(100% EXP penalty)
Ninja And Fibonacci Numbers
Full screen
Console