Code Implementation

class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        fibs = [1, 1]
        while fibs[-1] < k:
            fibs.append(fibs[-1] + fibs[-2])
        count = 0
        i = len(fibs) - 1
        while k > 0:
            if fibs[i] <= k:
                k -= fibs[i]
                count += 1
            i -= 1
        return count
      

class Solution {
public:
    int findMinFibonacciNumbers(int k) {
        vector<int> fibs = {1, 1};
        while (fibs.back() < k) {
            fibs.push_back(fibs.back() + fibs[fibs.size() - 2]);
        }
        int count = 0, i = fibs.size() - 1;
        while (k > 0) {
            if (fibs[i] <= k) {
                k -= fibs[i];
                count++;
            }
            i--;
        }
        return count;
    }
};
      

class Solution {
    public int findMinFibonacciNumbers(int 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));
        }
        int count = 0, i = fibs.size() - 1;
        while (k > 0) {
            if (fibs.get(i) <= k) {
                k -= fibs.get(i);
                count++;
            }
            i--;
        }
        return count;
    }
}
      

var findMinFibonacciNumbers = function(k) {
    const fibs = [1, 1];
    while (fibs[fibs.length - 1] < k) {
        fibs.push(fibs[fibs.length - 1] + fibs[fibs.length - 2]);
    }
    let count = 0, i = fibs.length - 1;
    while (k > 0) {
        if (fibs[i] <= k) {
            k -= fibs[i];
            count++;
        }
        i--;
    }
    return count;
};
      

Problem Description

Given a positive integer k, you are to find the minimum number of Fibonacci numbers whose sum is equal to k. Each Fibonacci number can be used at most once in the sum. Recall that the Fibonacci sequence is defined as F(1) = 1, F(2) = 1, F(n) = F(n-1) + F(n-2) for n > 2.

You must return the smallest count of Fibonacci numbers such that their sum equals exactly k. You cannot reuse any Fibonacci number, and it is guaranteed that there is always at least one valid solution for any valid input.

Thought Process

At first glance, this problem resembles the classic "coin change" problem, where you want to make a certain amount using the fewest coins, each with a limited supply (in this case, each Fibonacci number can be used once). The naive approach would be to try all combinations of Fibonacci numbers less than or equal to k and see which combination sums to k with the smallest count.

However, this brute-force approach is not efficient, especially as k grows large, because there are exponentially many combinations. The key insight is to notice that Fibonacci numbers form a special sequence, and there is a greedy way to build up the sum: always use the largest Fibonacci number not exceeding the remaining k, subtract it, and repeat until k becomes zero. This works because of a property known as Zeckendorf's Theorem, which states that every positive integer can be uniquely represented as a sum of non-consecutive Fibonacci numbers.

Solution Approach

We use a greedy algorithm to solve the problem efficiently. Here’s how the approach works step-by-step:

1. Generate Fibonacci Numbers:
   • First, generate all Fibonacci numbers up to k. We start with [1, 1] and keep adding the sum of the last two numbers until we reach or exceed k.
2. Iterative Greedy Selection:
   • Start from the largest Fibonacci number less than or equal to k.
   • Subtract this number from k and increment a counter.
   • Repeat the process with the new value of k (using the next largest Fibonacci number that does not exceed the current k).
   • Continue until k becomes zero.
3. Return the Counter:
   • The counter now contains the minimum number of Fibonacci numbers that sum to the original k.

This approach is efficient because at each step, we reduce k by the largest possible amount, minimizing the number of steps needed.

Example Walkthrough

Let’s walk through an example with k = 19:

1. Generate Fibonacci Numbers up to 19:
   [1, 1, 2, 3, 5, 8, 13, 21]
   (21 is greater than 19, so we only consider up to 13)
2. First Iteration:
   Largest Fibonacci ≤ 19 is 13. Subtract 13 from 19 → k = 6. Count = 1.
3. Second Iteration:
   Largest Fibonacci ≤ 6 is 5. Subtract 5 from 6 → k = 1. Count = 2.
4. Third Iteration:
   Largest Fibonacci ≤ 1 is 1. Subtract 1 from 1 → k = 0. Count = 3.
5. Done!
   The minimum number of Fibonacci numbers whose sum is 19 is 3 (13, 5, 1).

Time and Space Complexity

Brute-force Approach:

• Would involve checking all combinations of Fibonacci numbers ≤ k. This is exponential in the number of Fibonacci numbers (O(2^n)), which is not feasible for large k.

• Time Complexity: Generating Fibonacci numbers up to k takes O(log k) time, since Fibonacci numbers grow exponentially. The greedy selection step also takes O(log k) time, as we may subtract at most as many times as there are Fibonacci numbers ≤ k.
• Space Complexity: Storing the Fibonacci numbers up to k requires O(log k) space.

Overall, the greedy approach is highly efficient and suitable for the problem's constraints.

Summary

The problem of finding the minimum number of Fibonacci numbers whose sum is k can be solved efficiently using a greedy approach, thanks to Zeckendorf's Theorem. The solution involves generating all Fibonacci numbers up to k and iteratively subtracting the largest possible Fibonacci number until we reach zero. This method is both fast and elegant, leveraging the unique properties of the Fibonacci sequence to avoid brute-force search.