Minimum Fibonacci terms with sum equal to K | Function to calculate Fibonacci Terms ; Calculate all Fibonacci terms which are less than or equal to K . ; If next term is greater than K do not push it in vector and return . ; Function to find the minimum number of Fibonacci terms having sum equal to K . ; Vector to store Fibonacci terms . ; Subtract Fibonacci terms from sum K until sum > 0. ; Divide sum K by j - th Fibonacci term to find how many terms it contribute in sum . ; Driver code
def calcFiboTerms ( fiboTerms , K ) : NEW_LINE INDENT i = 3 NEW_LINE fiboTerms . append ( 0 ) NEW_LINE fiboTerms . append ( 1 ) NEW_LINE fiboTerms . append ( 1 ) NEW_LINE while True : NEW_LINE INDENT nextTerm = ( fiboTerms [ i - 1 ] + fiboTerms [ i - 2 ] ) NEW_LINE if nextTerm > K : NEW_LINE INDENT return NEW_LINE DEDENT fiboTerms . append ( nextTerm ) NEW_LINE i += 1 NEW_LINE DEDENT DEDENT def findMinTerms ( K ) : NEW_LINE INDENT fiboTerms = [ ] NEW_LINE calcFiboTerms ( fiboTerms , K ) NEW_LINE count , j = 0 , len ( fiboTerms ) - 1 NEW_LINE while K > 0 : NEW_LINE INDENT count += K // fiboTerms [ j ] NEW_LINE K %= fiboTerms [ j ] NEW_LINE j -= 1 NEW_LINE DEDENT return count NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT K = 17 NEW_LINE print ( findMinTerms ( K ) ) NEW_LINE DEDENT