Ninja And Fibonacci Numbers — Asked in Flipkart Interview

Problem Statement :

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 :

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

Approach :

  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

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

Upskilling students for tech placements!