Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

What is this problem about?

The Find the Minimum Number of Fibonacci Numbers Whose Sum Is K coding problem asks you to represent a given integer $k$ as a sum of the minimum possible number of Fibonacci numbers. You can use the same Fibonacci number multiple times? Actually, the problem usually specifies you can use each one multiple times or just distinct ones, but for Fibonacci, the greedy choice works for both.

Why is this asked in interviews?

Google uses this to test your ability to recognize when a Greedy approach is optimal. It requires knowing the Zeckendorf's Theorem, which states that every positive integer can be uniquely represented as a sum of non-consecutive Fibonacci numbers. It evaluations whether you can identify that always picking the largest Fibonacci number less than or equal to the current $k$ leads to the minimum count.

Algorithmic pattern used

This problem uses a Greedy strategy with Preprocessing.

1. Generate all Fibonacci numbers up to $k$ and store them in a list.
2. Starting from the largest Fibonacci number, subtract it from $k$ as many times as possible (if each can be used multiple times) or just once (if they must be distinct).
3. Each subtraction counts as one Fibonacci number used.
4. Continue until $k$ becomes 0.

Example explanation

$k = 19$. Fibonacci numbers: 1, 1, 2, 3, 5, 8, 13, 21...

1. Largest Fib $\le 19$ is 13. $19 - 13 = 6$. (Count = 1).
2. Largest Fib $\le 6$ is 5. $6 - 5 = 1$. (Count = 2).
3. Largest Fib $\le 1$ is 1. $1 - 1 = 0$. (Count = 3). Result: 3. (19 = 13 + 5 + 1).

Common mistakes candidates make

• Dynamic Programming: Using DP to solve it like the "Coin Change" problem. While correct, it's $O(K)$ which is too slow compared to the $O(\log K)$ greedy approach.
• List Generation: Forgetting to handle the starting 1, 1 sequence of Fibonacci.
• Redundant Checks: Not starting the subtraction from the largest values, which is the key to the greedy optimization.

Interview preparation tip

If you encounter a "Minimum items to reach sum K" problem where the items grow exponentially (like powers of 2 or Fibonacci numbers), always check if a Greedy approach works. For Fibonacci and powers of 2, it is always optimal.