#1414
Find the Minimum Number of Fibonacci Numbers Whose Sum Is K
specialist · 640 · lc medium +30 · verified · 64.8% accepted · 1,051 likes · top 68%
Description
Given an integer k, find the minimum number of Fibonacci numbers (repetition allowed) that sum to exactly k. The sequence begins F1 = 1, F2 = 1, Fn = Fn-1 + Fn-2 for n > 2. A valid decomposition always exists.
Example 1:
Input: k = 7
Output: 2
Explanation: The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, ...
For k = 7 we can use 2 + 5 = 7.
Example 2:
Input: k = 10
Output: 2
Explanation: For k = 10 we can use 2 + 8 = 10.
Example 3:
Input: k = 19
Output: 3
Explanation: For k = 19 we can use 1 + 5 + 13 = 19.
Code
1
2
3