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 :

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

--

--

More from Placewit

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Placewit

Upskilling students for tech placements!