Minimum Fibonacci terms with sum equal to K | C ++ code to find minimum number of fibonacci terms that sum 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void calcFiboTerms ( vector < int > & fiboTerms , int K ) { int i = 3 , nextTerm ; fiboTerms . push_back ( 0 ) ; fiboTerms . push_back ( 1 ) ; fiboTerms . push_back ( 1 ) ; while ( 1 ) { nextTerm = fiboTerms [ i - 1 ] + fiboTerms [ i - 2 ] ; if ( nextTerm > K ) return ; fiboTerms . push_back ( nextTerm ) ; i ++ ; } } int findMinTerms ( int K ) { vector < int > fiboTerms ; calcFiboTerms ( fiboTerms , K ) ; int count = 0 , j = fiboTerms . size ( ) - 1 ; while ( K > 0 ) { count += ( K / fiboTerms [ j ] ) ; K %= ( fiboTerms [ j ] ) ; j -- ; } return count ; } int main ( ) { int K = 17 ; cout << findMinTerms ( K ) ; return 0 ; }