Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

We can solve this problem by first generating Fibonacci numbers up to the given integer k, and then selecting the largest Fibonacci numbers that add up to k. Here’s the code for the solution class:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        fib = [1, 1]

        # Generate Fibonacci numbers up to k
        while fib[-1] + fib[-2] <= k:
            fib.append(fib[-1] + fib[-2])

        count = 0
        # Select the largest Fibonacci numbers that add up to k
        for num in reversed(fib):
            if k >= num:
                k -= num
                count += 1
            if k == 0:
                break

        return count

1. We initialize the Fibonacci sequence with the first two numbers 1 and 1.
2. We then generate the rest of the Fibonacci numbers up to k.
3. We iterate through the generated Fibonacci numbers in reverse order, selecting the largest numbers that fit into k, and subtracting them from k.
4. We continue this process until k becomes zero, and then return the count of the selected Fibonacci numbers.

The time complexity of this solution is O(log k) for generating the required Fibonacci numbers, and the space complexity is also O(log k) for storing the Fibonacci sequence.