Find the Minimum Number of Fibonacci Numbers Whose Sum Is K Solution
Find the Minimum Number of Fibonacci Numbers Whose Sum Is K solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Find the Minimum Number of Fibonacci Numbers Whose Sum Is K is a medium coding problem on math and greedy, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Math, Greedy
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The Fibonacci numbers are F1 = 1, F2 = 1 and Fn = Fn-1 + Fn-2 for n > 2: 1, 1, 2, 3, 5, 8, 13, …
Given an integer k, return the minimum number of Fibonacci numbers whose sum is exactly k. The same Fibonacci number may be used more than once. Such a sum always exists.
Example 1
Input: k = 7
Output: 2
Explanation: 7 = 2 + 5.
Example 2
Input: k = 10
Output: 2
Explanation: 10 = 2 + 8.
Example 3
Input: k = 19
Output: 3
Explanation: 19 = 1 + 5 + 13.
Constraints
1 <= k <= 10^9
Hints for Find the Minimum Number of Fibonacci Numbers Whose Sum Is K
Hint 1
Try taking the largest Fibonacci number that does not exceed
k, then repeat on what is left.Hint 2
Why is that safe? An optimal sum never needs two consecutive Fibonacci numbers (replace them by their sum) nor the same number twice (2·Fn = Fn+1 + Fn-2).
Hint 3
A sum of non-consecutive, distinct Fibonacci numbers below
F(m+1)cannot reachF(m+1), so the largest Fibonacci number ≤ k must be in it.
How to solve Find the Minimum Number of Fibonacci Numbers Whose Sum Is K
Greedy works: repeatedly subtract the largest Fibonacci number not exceeding the remainder (Zeckendorf's representation).
Approach
- List the Fibonacci numbers up to
k. - Walk the list from the largest: whenever the current number fits in the remainder, subtract it and count it.
- Stop when the remainder is 0 and return the count.
Why it works
Among optimal sums take one with the fewest terms that also avoids two consecutive Fibonacci numbers (merging Fn + Fn+1 into Fn+2 reduces the count) and repeated ones (2·Fn = Fn+1 + Fn-2 keeps the count but removes the repeat, and the process terminates). The largest possible sum of distinct, non-consecutive Fibonacci numbers all below F(m) is F(m) − 1, so if the largest Fibonacci number F(m) ≤ k were missing the terms could not reach k. Hence an optimal sum contains it, and induction on k − F(m) finishes the proof. After subtracting F(m) the remainder is below F(m−1), so the scan never needs to revisit a number.
Complexity
- Time —
O(log k) — there are about 44 Fibonacci numbers up to 10^9 - Space —
O(log k)
Pitfalls
- A coin-change DP is correct but needs O(k) memory, impossible for 10^9.
- Generating Fibonacci numbers past
k: the next one after 701,408,733 is 1,134,903,170, still inside int32, but stop before overflowing. - The two leading 1s are the same value; one copy in the list is enough.
Reference solution
Python
def findMinFibonacciNumbers(k: int) -> int:
fib = [1, 2]
while fib[-1] + fib[-2] <= k:
fib.append(fib[-1] + fib[-2])
count = 0
for f in reversed(fib):
if f <= k:
k -= f
count += 1
if k == 0:
break
return countJava
public static int findMinFibonacciNumbers(int k) {
List<Long> fib = new ArrayList<>();
fib.add(1L);
fib.add(2L);
while (fib.get(fib.size() - 1) + fib.get(fib.size() - 2) <= k) fib.add(fib.get(fib.size() - 1) + fib.get(fib.size() - 2));
long rest = k;
int count = 0;
for (int i = fib.size() - 1; i >= 0 && rest > 0; i--) {
if (fib.get(i) <= rest) {
rest -= fib.get(i);
count++;
}
}
return count;
}C++
int findMinFibonacciNumbers(int k) {
vector<long long> fib = {1, 2};
while (fib[fib.size() - 1] + fib[fib.size() - 2] <= k) fib.push_back(fib[fib.size() - 1] + fib[fib.size() - 2]);
long long rest = k;
int count = 0;
for (int i = (int)fib.size() - 1; i >= 0 && rest > 0; i--) {
if (fib[i] <= rest) {
rest -= fib[i];
count++;
}
}
return count;
}JavaScript
var findMinFibonacciNumbers = function(k) {
var fib = [1, 2];
while (fib[fib.length - 1] + fib[fib.length - 2] <= k) fib.push(fib[fib.length - 1] + fib[fib.length - 2]);
var count = 0;
for (var i = fib.length - 1; i >= 0 && k > 0; i--) {
if (fib[i] <= k) {
k -= fib[i];
count++;
}
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Greedy Algorithms