Description
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 = 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 up to 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:
Solutions
Solution 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)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | 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);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12 | 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);
}
};
|
| 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)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | 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;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | 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
}
}
|