Last Updated: 13 Apr, 2021
Ninja And Fibonacci Numbers
Easy
Asked in companies
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’.
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
Approaches
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:
- Base Case: If ‘SUM’ is less than 2 return ‘SUM’.
- Declare two variables ‘a’ = 1 and ‘b’ = 1.
- While ‘b’ <= ‘SUM’ :
- ‘b’ = ‘b’ + a.
- ‘a’ = ‘b’ - ‘a’.
- Finally, return 1 + findMinFibNums(‘SUM’ - ‘a’).
First, we find all the Fibonacci numbers till ‘SUM’. Then we keep subtracting the maximum Fibonacci numbers less than or equal to ‘SUM’ and update the count.
The steps are as follows:
- Declare a vector/list ‘temp’ of size 2 and initialize it with 1.
- Run a loop for ‘i’ = 2 to ‘SUM’:
- ‘X’ = ‘temp[i - 1]’ + ‘temp[i - 2]’.
- If ‘X’ is greater than ‘SUM’:
- Break.
- Add ‘X’ in ‘temp’.
- Declare a variable ‘count’ and initialize it with 0.
- Declare a variable ‘end’ pointing to the end of ‘temp’.
- While ‘SUM’ greater than 0:
- ‘si’ = find the minimum index which is greater than and equal to the ‘SUM’.
- If ‘si’ == ‘end’:
- Decrement ‘end’ by 1.
- ‘SUM’ -= ‘end’.
- Else if ‘si’ is equal to ‘SUM’:
- ‘SUM’ = 0.
- Else:
- Decrement ‘si’ by 1.
- ‘SUM’ = ‘SUM’ - ‘si’.
- Decrement ‘si’ by 1.
- ‘end’ = ‘si’.
- Increment ‘count’ by 1.
- Finally, return ‘count’.
We are only converting the above recursive approach into an iterative approach.
The steps are as follows:
- Declare three variables ‘a’ = 1,‘b’ = 1 and ‘ans’ = 0.
- While ‘b’ less than equal to ‘SUM’:
- ‘temp’ = ‘a’.
- ‘a’ = ‘b’.
- ‘b’ = ‘temp’+’b’.
- While ‘a’ greater than 0:
- If ‘a’ is less than or equal to ‘SUM’:
- ‘SUM’ = ‘SUM’ - ‘a’.
- ‘ans’ = ‘ans’ + 1.
- ‘temp’ = ‘a’.
- ‘a’ = ‘b’ - ‘a’.
- ‘b’ = ‘temp’.
- If ‘a’ is less than or equal to ‘SUM’:
- Finally, return ‘ans’.