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 = 1F2 = 1Fn = Fn-1 + Fn-2 for n > 2.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 <= 109Problem Overview: You are given an integer k. The goal is to represent k as the sum of Fibonacci numbers using the minimum possible count. Each Fibonacci number can be used multiple times, and you want the smallest number of terms whose total equals k.
Approach 1: Greedy with Fibonacci Generation (O(log k) time, O(log k) space)
This problem works well with a greedy strategy. First generate all Fibonacci numbers less than or equal to k. The key observation is that subtracting the largest Fibonacci number not exceeding the current value always leads to an optimal solution. After subtracting it, repeat the same step with the remaining value until it reaches zero. Because Fibonacci numbers grow exponentially, there are only about 45 values up to 10^9, so generation and iteration are both very small.
The algorithm works as follows: build a Fibonacci list using iteration, then repeatedly find the largest value ≤ k, subtract it, and increment a counter. This greedy choice works due to properties of Fibonacci numbers (related to Zeckendorf’s theorem), which guarantees that every integer has a unique representation as a sum of non‑consecutive Fibonacci numbers. Time complexity is O(log k) because the Fibonacci sequence length grows logarithmically with k. Space complexity is also O(log k) for storing the sequence. This approach mainly relies on concepts from greedy algorithms and math.
Approach 2: Dynamic Programming / Coin Change Style (O(F × k) time, O(k) space)
You can also frame the problem as a variation of the coin change problem. Treat each Fibonacci number ≤ k as a coin denomination and compute the minimum number of coins needed to reach exactly k. First generate all Fibonacci numbers up to k. Then build a DP array where dp[i] stores the minimum numbers required to form sum i. For each Fibonacci value, iterate through the DP array and update states similar to unbounded knapsack.
This method guarantees correctness because it explores every combination of Fibonacci numbers. However, the state space grows with k, which makes it impractical for large values such as 10^9. Time complexity becomes O(F × k), where F is the number of Fibonacci numbers ≤ k (around 45). Space complexity is O(k). The approach demonstrates classic dynamic programming reasoning but is usually unnecessary given the greedy property.
Recommended for interviews: The greedy approach is the expected solution. Interviewers want to see that you generate Fibonacci numbers efficiently and repeatedly subtract the largest valid value. Mentioning the mathematical property that guarantees optimality strengthens the explanation. A DP formulation shows broader problem‑solving ability, but the greedy solution demonstrates deeper insight and achieves optimal O(log k) performance.
This approach uses a greedy strategy to select the largest possible Fibonacci number that is less than or equal to the target sum, k, repeatedly until the remainder is zero. This ensures that the sum converges towards k quickly.
In this solution, we first generate a list of Fibonacci numbers up to the largest one less than or equal to k. Then, starting from the largest Fibonacci number, we subtract it from k until k reaches zero, increasing our count each time. The number of subtractions required gives us the minimum count of Fibonacci numbers needed to sum up to k.
Time Complexity: O(log k) because the number of Fibonacci numbers is logarithmic relative to k.
Space Complexity: O(log k) for storing the Fibonacci sequence.
This approach involves using dynamic programming to build a solution by storing previously calculated results in an array to calculate the fewest sum of Fibonacci numbers that make up a number.
This Java solution demonstrates a similar logic where Fibonacci numbers are first generated, then used to minimize the count by subtracting from k using the largest possible Fibonacci numbers iteratively.
Java
Time Complexity: O(log k).
Space Complexity: O(log k).
We can greedily select the largest Fibonacci number that does not exceed k each time, then subtract this number from k and increment the answer by one. This process is repeated until k = 0.
Since we greedily select the largest Fibonacci number that does not exceed k each time, suppose this number is b, the previous number is a, and the next number is c. Subtracting b from k results in a value that is less than a, which means that after selecting b, we will not select a. This is because if we could select a, then we could have greedily selected the next Fibonacci number c instead of b earlier, which contradicts our assumption. Therefore, after selecting b, we can greedily reduce the Fibonacci number.
The time complexity is O(log k), and the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Greedy Approach with Fibonacci Generation | Time Complexity: O(log k) because the number of Fibonacci numbers is logarithmic relative to k. |
| Dynamic Programming Approach | Time Complexity: O(log k). |
| Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Fibonacci Generation | O(log k) | O(log k) | Best approach for large k. Uses the largest Fibonacci ≤ remaining value each step. |
| Dynamic Programming (Coin Change) | O(F × k) | O(k) | Useful for understanding the problem as a coin change variant or when constraints on k are small. |
Leetcode 1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K • Fraz • 5,859 views views
Watch 7 more video solutions →Practice Find the Minimum Number of Fibonacci Numbers Whose Sum Is K with our built-in code editor and test cases.
Practice on FleetCode