Minimum numbers required from fibonacci series to sum upto N ?


  • 0
    N

    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


  • 0

    It seems to me that this is a modified version of Combination Sum, we just have to pre-generate the fibonacci sequence till N, and the solution can be found here.


  • 0

    I think there must be a way to take advantage of the fact that it's the Fibonacci sequence. You would for example never use two consecutive Fibonacci numbers in an optimal solution, because you could just replace them with their sum.


  • 0

    You are right! This is a very interesting problem.


  • 0
    9
    int Solution::fibsum(int A) 
    {
        vector<int> fib;
    	int count = 0;
    	int a = 1,b = 1;
    	
    	while(a <= A)
    	{
    		fib.push_back(a);
    		int temp = a+b;
    		a = b;
    		b = temp;
    	}
    	
    	for(int i = fib.size()-1; i >= 0; i--)
    	{
    		int num = fib[i];
    		while(num <= A)
    		{
    			A = A-num;
    			count++;
    		}
    		if(A == 0)
    		{
    			break;
    		}
    	}
    	
    	return count;
    //https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.