##### 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

Related Topics:
Array, Greedy

## 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>();
int prev2 = 1, prev1 = 1;
int num = 2;
while (num <= k) {
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
}
}