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 <= 10^9

Difficulty: interview

Starter code:

class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        

Solutions:
class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        fib = [1, 1] # initializing a Fibonacci table with F[0] and F[1]
        i = 1 # index that will represent the last filled index of table
        temp = fib[0] + fib[1] # initial value of values to be appended
        while temp < k: # we keep filling table until temp >= k
            fib.append(temp) # add the current value to the table
            i += 1 # increase i by 1 to keep track of the last filled index
            temp = fib[i] + fib[i-1] # calculate new temp
        fib.append(temp) # to cover case temp == k, we append the last value >= k
    
        ans = 0 # initializing answer value with 0
        j = -1 # placeholder to represent last checked Fibonacci table index
        while k > 0: # keep repeating until k <= 0
            temp = fib[j] # get the biggest number available 
            j -= 1 # decrease j by 1 since we tried the last number
            
            if temp <= k:
                ans+=1
                k-=temp
      
        return ans

class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        a = b = 1
        fibo = [a,b]
      
        res = 0
        while a + b <= k:
            fibo.append(a + b)
            a, b = b, a+b
        for i in fibo[::-1]:
            if k >= i:
                k -= i
                res +=1
        return res
            
            
        


class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        f = []
        f.append(1)
        f.append(1)
        while 1:
            if max(f) <= k:
                f.append(f[len(f)-1] + f[len(f)-2])
            else:
                break
        f.remove(f[len(f)-1])

        number = 0
        while k != 0:
            if f[len(f)-1] <= k:
                k -= f[len(f)-1]
                f.remove(max(f))
                number += 1
            else:
                f.remove(max(f))

        return number

class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        first = 1
        second = 1
        
        fib = []
        
        i = 0
        while True:
            if i == 0:
                fib.append(1)
            elif i == 1:
                fib.append(1)
            else:
                val = fib[i - 1] + fib[i - 2]
                if val > k: break
                fib.append(val)
            i += 1
        print(fib)
        accum = 0
        ct = 0
        for i in range(len(fib) - 1, -1 , -1):
            accum += fib[i]
            if accum == k:
                ct += 1
                break
            elif accum > k:
                accum -= fib[i]
            else:
                ct += 1
        return ct


class Solution:
      
    def findMinFibonacciNumbers(self, k: int) -> int:
      grid = [1,1]
      last = 1
      while last < k:
        target = grid[-1] + grid[-2]
        if target > k: break
        else:
          grid.append(grid[-1] + grid[-2])
          last = grid[-1]
      res = 0
      ends = len(grid)-1
      while k > 0:
        while grid[ends] > k: ends -= 1
        k -= grid[ends]
        ends -= 1
        res += 1
      return res


class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        if k < 2:
            return k
        f1, f2 = 1, 1
        while f2 <= k:
            f1, f2 = f2, f1 + f2
        t = 0
        while k:
            # print(f1, f2, k, t)
            if f2 <= k:
                k -= f2
                t += 1
            else:
                f1, f2 = f2 - f1, f1
        return t


class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        
        a,b = 1,1
        while b<=k:
            a,b = b, a+b
        
        res = 0
        while a > 0:
            if k >= a:
                k -= a
                res += 1
            a,b = b-a, a 
            
        
        return res
        
        
        
        
#         if k == 0:
#             return 0
        
#         a,b = 1, 1
#         while b <= k:  # O( (logk)^2 )  
#             a,b = b, a+b
#         return self.findMinFibonacciNumbers(k-a)+1
    
    # First recursion, logk. Second resursion logK - 1, third entry logK - 2.
        
        
#         arr = [1, 1]
#         while arr[-1] <= k:
#             arr.append( arr[-1]+arr[-2] )   # O(n) space
        
#         d = k-arr[-2]
        
#         cnt = 1
        
#         while d > 0:
#             ind = bisect.bisect_right(arr, d)  # O(n log n) 
#             d -= arr[ind-1]
#             cnt += 1
        
#         return cnt
        


class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        fibo=[]
        fibo.append(1)
        fibo.append(1)
        lenn=2
        while fibo[-1]<=k:
            fibo.append(fibo[lenn-1]+fibo[lenn-2])
            lenn+=1
        
        nums=k
        cnt=0
        for i in range(len(fibo)-1, -1, -1):
            while nums>=fibo[i]:
                nums-=fibo[i]
                cnt+=1
            if nums==0:
                break
        return cnt

class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        
        if k == 0:
            return 0
        
        a,b = 1, 1
        while b <= k:
            a,b = b, a+b
        return self.findMinFibonacciNumbers(k-a)+1
        
        
#         arr = [1, 1]
#         while arr[-1] <= k:
#             arr.append( arr[-1]+arr[-2] )   # O(n) space
        
#         d = k-arr[-2]
        
#         cnt = 1
        
#         while d > 0:
#             ind = bisect.bisect_right(arr, d)  # O(n log n) 
#             d -= arr[ind-1]
#             cnt += 1
        
#         return cnt
        


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

class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        fib = [1,1]
        while(fib[-1]<k):
            fib.append(fib[-1]+fib[-2])
        print(fib)
        if k in fib:
            return 1
        cnt =0
        for i in range(len(fib)-1,-1,-1):
            print(('cnt ',cnt,'i ',i, fib[i],'k ',k))
            if fib[i]<=k:
                k = k-fib[i]
                cnt+=1
            if k==0:
                break
        return cnt
            
        


class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        fib = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,
               987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 
               75025, 121393, 196418, 317811, 514229, 832040, 1346269, 
               2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 
               39088169, 63245986, 102334155, 165580141, 267914296, 
               433494437, 701408733]
        ans = 0
        j= -1
        while k>0:
            tmp = fib[j]
            j-=1
            if tmp<=k:
                ans+=1
                k-=tmp
        return ans