# Find the Minimum Number of Fibonacci Numbers Whose Sum Is K
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k)
Canonical: https://scaleengineer.com/dsa/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
---
## Problem
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:**

* `1 <= k <= 109`

# Approaches
## Dynamic Programming (Time Limit Exceeded)
A standard approach for problems that ask for the minimum number of items to form a specific sum is dynamic programming. We can define `dp[i]` as the minimum number of Fibonacci numbers that sum to `i`. By building up the solution for `k` from smaller subproblems, we can find the answer. However, this approach is too slow and memory-intensive for the given constraints on `k`.
**Time:** O(k * log k) - The outer loop runs `k` times, and the inner loop iterates through the Fibonacci numbers, of which there are `O(log k)` up to `k`. This is too slow for `k = 10^9`. · **Space:** O(k) - We need an array of size `k+1` to store the DP states. For `k = 10^9`, this is not feasible.
**Pros:** It's a standard and straightforward application of dynamic programming.; Guaranteed to find the optimal solution for any similar change-making problem.
**Cons:** Highly inefficient for large `k`.; The time complexity of `O(k * log k)` is too slow for the given constraints, leading to a Time Limit Exceeded (TLE) error.; The space complexity of `O(k)` requires a very large amount of memory for `k` up to 10^9, leading to a Memory Limit Exceeded (MLE) error.
### Explanation
This method involves building a table of solutions for all values from 1 to `k`. We define `dp[i]` as the minimum count of Fibonacci numbers that sum up to `i`.

The process is as follows:
1.  Generate all unique Fibonacci numbers less than or equal to `k`.
2.  Create a `dp` array of size `k + 1` and initialize all its values to infinity, except for `dp[0]`, which is 0 (since 0 requires zero Fibonacci numbers).
3.  We then fill the `dp` table iteratively. For each number `i` from 1 to `k`, we try to form it by adding a Fibonacci number `f` to a previously computed sum `i - f`. The number of Fibonacci numbers for `i` would be `1 + dp[i - f]`. We do this for all possible Fibonacci numbers `f <= i` and take the one that results in the minimum count.
4.  The final result is stored in `dp[k]`.

While correct, the large value of `k` makes this approach impractical.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int findMinFibonacciNumbers(int k) {
        // This approach is too slow and memory-intensive for the given constraints.
        // It is provided for illustrative purposes.

        // Generate unique Fibonacci numbers up to k
        List<Integer> fibs = new ArrayList<>();
        int a = 1, b = 1;
        fibs.add(1);
        while (b <= k) {
            int temp = a + b;
            a = b;
            b = temp;
            if (b <= k) {
                fibs.add(b);
            }
        }

        int[] dp = new int[k + 1];
        Arrays.fill(dp, k + 1); // Initialize with a value larger than any possible answer
        dp[0] = 0;

        for (int i = 1; i <= k; i++) {
            for (int fib : fibs) {
                if (i >= fib) {
                    dp[i] = Math.min(dp[i], 1 + dp[i - fib]);
                } else {
                    break; // Optimization as fibs is sorted
                }
            }
        }
        return dp[k];
    }
}
```
### Algorithm
- First, generate all Fibonacci numbers `f` such that `f <= k`.
- Create a DP array, `dp`, of size `k + 1`. `dp[i]` will store the minimum number of Fibonacci numbers needed to form the sum `i`.
- Initialize `dp[0] = 0` and all other `dp[i]` to a large value (infinity).
- Iterate from `i = 1` to `k`. For each `i`, iterate through the generated Fibonacci numbers `f`.
- The recurrence relation is `dp[i] = min(dp[i], 1 + dp[i - f])` for every Fibonacci number `f <= i`.
- The final answer is `dp[k]`.

## Greedy Algorithm
A much more efficient solution is a greedy algorithm. The core idea is to always subtract the largest possible Fibonacci number from the remaining value of `k`. This works because of a special property of Fibonacci numbers which guarantees that this greedy choice is always part of an optimal solution. This method is extremely fast and uses minimal memory, making it ideal for the given constraints.
**Time:** O(log k) - Generating the Fibonacci numbers takes `O(log k)` time. The greedy subtraction loop also takes `O(log k)` time as it iterates through the list of Fibonacci numbers once. · **Space:** O(log k) - We need to store the list of Fibonacci numbers up to `k`. The number of such Fibonacci numbers is proportional to `log(k)`.
**Pros:** Extremely efficient, with logarithmic time and space complexity.; Simple to implement once the greedy strategy is known.; Easily handles the large constraints on `k`.
**Cons:** The correctness of the greedy approach is not immediately obvious and relies on a specific mathematical property of Fibonacci numbers (related to Zeckendorf's theorem).
### Explanation
The greedy strategy is based on the insight that to minimize the number of terms in a sum, one should use the largest possible numbers first. For Fibonacci numbers, this strategy is proven to be optimal.

The algorithm proceeds as follows:
1.  First, we generate all Fibonacci numbers that are less than or equal to `k`. Since Fibonacci numbers grow exponentially, this list will be small (fewer than 50 numbers for `k` up to 10^9).
2.  We initialize a counter to 0.
3.  We iterate from the largest generated Fibonacci number downwards. At each step, we check if the current Fibonacci number `f` can be subtracted from the remaining `k` (i.e., `f <= k`).
4.  If it can, we perform the subtraction (`k = k - f`) and increment our counter. This greedy choice is optimal because any sum of smaller Fibonacci numbers that could replace `f` would require more terms.
5.  We repeat this until `k` becomes 0. The final count is our answer.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int findMinFibonacciNumbers(int k) {
        // Step 1: Generate Fibonacci numbers up to k.
        List<Integer> fibs = new ArrayList<>();
        fibs.add(1);
        fibs.add(1);
        while (fibs.get(fibs.size() - 1) < k) {
            int n = fibs.size();
            fibs.add(fibs.get(n - 1) + fibs.get(n - 2));
        }

        // Step 2: Use a greedy approach to find the minimum number of terms.
        int count = 0;
        int i = fibs.size() - 1;
        while (k > 0) {
            if (fibs.get(i) <= k) {
                k -= fibs.get(i);
                count++;
            }
            i--;
        }
        return count;
    }
}
```
### Algorithm
- Generate Fibonacci numbers `F_1, F_2, ...` and store them in a list `fibs` until the generated number is greater than `k`.
- Initialize a counter `count = 0`.
- Start from the largest number in `fibs` and move downwards (e.g., using an index `i` from `fibs.size() - 1` to 0).
- While `k > 0`:
  - If the current Fibonacci number `fibs.get(i)` is less than or equal to `k`:
    - Subtract it from `k`: `k = k - fibs.get(i)`.
    - Increment the counter: `count = count + 1`.
  - Move to the next smaller Fibonacci number: `i = i - 1`.
- Return `count`.

# Solutions
### Java

```java
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);
  }
}

```

### CPP

```cpp
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);
  }
};

```

### Python

```python
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)

```