Given an integer&nbsp;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 &gt; 2.

It is guaranteed that for the given constraints we can always find such Fibonacci numbers that sum up to k.
&nbsp;
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.


&nbsp;
Constraints:


	1 &lt;= k &lt;= 109


class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        fib_sq = [1, 1]
        while fib_sq[-1] + fib_sq[-2] <= k:
            fib_sq.append(fib_sq[-1]+fib_sq[-2])
        counter = 0
        for i in range(len(fib_sq)-1, -1, -1):
            if fib_sq[i] <= k:
                counter += 1
                k -= fib_sq[i]
        return counter
class Solution {
    public int findMinFibonacciNumbers(int k) {
        int ans = 0;

        while (k > 0) {
			// Run until solution is reached
            int fib2prev = 1;
            int fib1prev = 1;
            while (fib1prev <= k) {
				// Generate Fib values, stop when fib1prev is > k, we have the fib number we want stored in fib2prev
                int temp = fib2prev + fib1prev;
                fib2prev = fib1prev;
                fib1prev = temp;
            }
            k -= fib2prev;
            ans += 1;
        }
        return ans;
    }
}
class Solution
{
public:
    int findMinFibonacciNumbers(int k)
    {
        vector<int> fibb;
        int a = 1;
        int b = 1;
        fibb.push_back(a);
        fibb.push_back(b);
        int next = a + b;

        while (next <= k)
        {
            fibb.push_back(next);
            a = b;
            b = next;
            next = a + b;
        }

        int res = 0;
        int j = fibb.size() - 1;
        while (j >= 0 and k > 0)
        {
            if (fibb[j] <= k)
            {
                k -= fibb[j];
                res++;
            }
            j--;
        }

        return res;
    }
};
var findMinFibonacciNumbers = function(k) {
    let sequence = [1, 1], sum = sequence[0] + sequence[1];
    let i = 2;
    while (sum <= k) {
        sequence.push(sum);
        i++;
        sum = sequence[i-1]+sequence[i-2];
    }
    let j = sequence.length-1, res = 0;
    while (k) {
        if (k >= sequence[j]) k -= sequence[j], res++;
        j--;
    }
    return res;
    // Time Complexity: O(n)
    // Space Complexity: O(n)
};
Find the Minimum Number of Fibonacci Numbers Whose Sum Is K