Medium
Quiz
#1414 Find the Minimum Number of Fibonacci Numbers Whose Sum Is K
APPROACH
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.
1 of 4
1:00
What is the optimal approach for this problem?