Watch 10 video solutions for Find the Minimum Number of Fibonacci Numbers Whose Sum Is K, a medium level problem involving Math, Greedy. This walkthrough by Nick White has 21,761 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer k, return the minimum number of Fibonacci numbers whose sum is equal to k. The same Fibonacci number can be used multiple times.
The Fibonacci numbers are defined as:
F1 = 1F2 = 1Fn = Fn-1 + Fn-2 for n > 2.k.
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.
Constraints:
1 <= k <= 109