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.

--

--

--

Upskilling students for tech placements!

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

Recommended from Medium

Nine must-have Twitch Extension features

專案管理爬文簡記

Backup and Recovery Solution for Disk-based Data Volumes in Kubernetes Clusters

Introduction to Apache Flume

Deploying Hello World on Cloud Foundry Without Any Coding

Power Automate: Create SharePoint to SQL Data Pipeline From a Scratch

Microsoft Power Automate

Battle Training #1 - Remove Liquidity

Amazon S3 Overview

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!

More from Medium

Minimum Operations to Reduce X to Zero — LeetCode

Path With Minimum Effort

Best Time to Buy and Sell Stock: Leetcode — Blind 75 (Sliding Window)

Leetcode Solutions — 2Sums