Find the Minimum Number of Fibonacci Numbers Whose Sum Is K - Video Solutions

Problem 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.