Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1414.html
1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K (Medium)
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 1. Greedy
We greedily find the maximum fibonacci number that is smaller or equal to k
.
Assume it’s b
, then f(k) = f(k-b) + 1
. f(0) = 0
.
// OJ: https://leetcode.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/
// Time: O(F(k)) where F(k) is the steps to compute the fibonacci number greater than k
// Space: O(1)
class Solution {
public:
int findMinFibonacciNumbers(int k) {
if (k == 0) return 0;
int a = 1, b = 1;
while (a + b <= k) {
int c = a + b;
a = b;
b = c;
}
return findMinFibonacciNumbers(k - b) + 1;
}
};
-
class Solution { public int findMinFibonacciNumbers(int k) { TreeSet<Integer> set = new TreeSet<Integer>(); set.add(0); set.add(1); int prev2 = 1, prev1 = 1; int num = 2; while (num <= k) { set.add(num); prev2 = prev1; prev1 = num; num = prev2 + prev1; } int count = 0; while (k > 0) { int fibo = set.floor(k); k -= fibo; count++; } return count; } } ############ class Solution { public int findMinFibonacciNumbers(int k) { if (k < 2) { return k; } int a = 1, b = 1; while (b <= k) { b = a + b; a = b - a; } return 1 + findMinFibonacciNumbers(k - a); } }
-
// OJ: https://leetcode.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/ // Time: O(F(k)) where F(k) is the steps to compute the fibonacci number greater than k // Space: O(1) class Solution { public: int findMinFibonacciNumbers(int k) { if (k == 0) return 0; int a = 1, b = 1; while (a + b <= k) { int c = a + b; a = b; b = c; } return findMinFibonacciNumbers(k - b) + 1; } };
-
class Solution: def findMinFibonacciNumbers(self, k: int) -> int: def dfs(k): if k < 2: return k a = b = 1 while b <= k: a, b = b, a + b return 1 + dfs(k - a) return dfs(k) ############ class Solution: def findMinFibonacciNumbers(self, k: int) -> int: fib = [1, 1] while fib[-1] < k: fib.append(fib[-1] + fib[-2]) res = 0 while k != 0: for i in range(len(fib) - 1, -1, -1): if fib[i] <= k: k -= fib[i] res += 1 break return res
-
func findMinFibonacciNumbers(k int) int { if k < 2 { return k } a, b := 1, 1 for b <= k { a, b = b, a+b } return 1 + findMinFibonacciNumbers(k-a) }
-
const arr = [ 1836311903, 1134903170, 701408733, 433494437, 267914296, 165580141, 102334155, 63245986, 39088169, 24157817, 14930352, 9227465, 5702887, 3524578, 2178309, 1346269, 832040, 514229, 317811, 196418, 121393, 75025, 46368, 28657, 17711, 10946, 6765, 4181, 2584, 1597, 987, 610, 377, 233, 144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1, ]; function findMinFibonacciNumbers(k: number): number { let res = 0; for (const num of arr) { if (k >= num) { k -= num; res++; if (k === 0) { break; } } } return res; }
-
const FIB: [i32; 45] = [ 1836311903, 1134903170, 701408733, 433494437, 267914296, 165580141, 102334155, 63245986, 39088169, 24157817, 14930352, 9227465, 5702887, 3524578, 2178309, 1346269, 832040, 514229, 317811, 196418, 121393, 75025, 46368, 28657, 17711, 10946, 6765, 4181, 2584, 1597, 987, 610, 377, 233, 144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1, ]; impl Solution { pub fn find_min_fibonacci_numbers(mut k: i32) -> i32 { let mut res = 0; for &i in FIB.into_iter() { if k >= i { k -= i; res += 1; if k == 0 { break; } } } res } }