# 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:**

- Declare three variables ‘a’ = 1,‘b’ = 1 and ‘ans’ = 0.
- 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)