Ninja And Fibonacci Numbers — Asked in Flipkart Interview

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’.

Sample Input:

15

Sample Output:

2

Explanation of given Test Cases :

As we know Fibonacci series is: 1, 1, 2, 3, 5, 8, 13, 21, 34

In the given test case, for ‘SUM’ = 15 we can use only 13 + 2 = 15.

Approach :

The steps are as follows:

1. Declare three variables ‘a’ = 1,‘b’ = 1 and ‘ans’ = 0.
2. While ‘b’ less than equal to ‘SUM’:

• ‘temp’ = ‘a’.
• ‘a’ = ‘b’.
• ‘b’ = ‘temp’+’b’.

3. 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’.

4. Finally, return ‘ans’.

Time complexity: O(log(SUM))
Space complexity: O(1)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.