Leetcode 1515 Solution

This article provides solution to leetcode question 1515 (find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k)
Categories:
Tags:
Access this page by simply typing in "lcs 1515" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k

Solution

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

        ans = 0
        index = len(a) - 1
        while index >= 0 and k > 0:
            if k >= a[index]:
                k -= a[index]
                ans += 1
            index -= 1
        return ans