Given the number k, return the minimum number of Fibonacci numbers whose sum is equal to k, whether a Fibonacci number could be used multiple times.
The Fibonacci numbers are defined as:
- F1 = 1
- F2 = 1
- Fn = Fn-1 + Fn-2 , for n > 2.
It is guaranteed that for the given constraints we can always find such fibonacci numbers that sum 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 <= 10^9
Solution: Greedy
Find the largest fibonacci numbers x that x <= k, ans = 1 + find(k – x)
Time complexity: O(logk^2) -> O(logk)
Space complexity: O(logk) -> O(1)
Recursive
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public: int findMinFibonacciNumbers(int k) { if (k == 0) return 0; int f1 = 1; int f2 = 1; while (f2 <= k) { swap(f1, f2); f2 += f1; } return 1 + findMinFibonacciNumbers(k - f1); } }; |
Iterative
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua class Solution { public: int findMinFibonacciNumbers(int k) { int f1 = 1; int f2 = 1; int ans = 1; while (f2 <= k) { swap(f1, f2); f2 += f1; } k -= f1; while (k) { if (k >= f1) { k -= f1; ans += 1; } f2 -= f1; swap(f1, f2); } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment