Problem Statement

How many minimum numbers from fibonacci series are required such that sum of numbers should be equal to a given Number N?Note : repetition of number is allowed.

Example:

N = 4 Fibonacci numbers : 1 1 2 3 5 .... so on here 2 + 2 = 4 so minimum numbers will be 2

Problem Link

Sum Of Fibonacci Numbers - InterviewBit

Reference Link

Minimum Fibonacci terms with sum equal to K - GeeksforGeeks

Code

int Solution::fibsum(int A) {
    
    vector<int> fiboterm;
    int a = 0,b = 1,c = 1;
    fiboterm.push_back(b);
    fiboterm.push_back(c);
    
    while(c<A)
    {
        c = a+b;
        a=b;
        b=c;
        fiboterm.push_back(c);
    }
    int count = 0,i =fiboterm.size()-1;
    while(A>0)
    {
        count += A/fiboterm[i];
        A = A%fiboterm[i];
        i--;
    }
    return count;
}