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
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:
        
        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
        
