Google | Onsite | Min number of Fibonacci terms with sum equal to a given number
2445

Question:
Given a non-negative integer n, write a function to test if that n is a Fibonacci number.

Example 1:

Input: n = 13
Output: true

Example 2:

Input: n = 20
Output: false

Follow-up:
All positive integer numbers can be represented as a sum of Fibonacci numbers. Given a non-negative integer n, find any minimum combination of Fibonacci numbers required that sums up to a given number n.

Example 1:

Input: n = 14
Output: [1, 13]
Explanation: 1+13, 8+5+1, 3+5+5+1 and many others can sum up to 14, but minimum number of terms required are 2.

Example 2:

Input: n = 17
Output: [1, 3, 13] or [8, 8, 1] or [13, 2, 2]
Explanation: 1+3+13, 8+8+1, 13+2+2 all sum up to 17 and 3 is minimum number of terms required so you can return any of them.

Example 3:

Input: n = 20
Output: [13, 5, 2]

Related problems:

Comments (6)