Minimum number of Fibonacci terms with sum equal to a given number N

Reading time: 25 minutes | Coding time: 5 minutes

The problem we will solve is that given a number N, we need to find the minimum number of fibonacci numbers required that sums up to a given number N. Note a fibonacci number can be repeated. We will solve this problem efficiently using a greedy technique in O(log N) time.

This problem is like an easy version to the problem "Number of ways to represent a number N as sum of K Fibonacci terms". You may visit that problem here:

Number of ways to represent a number N as sum of K Fibonacci terms

Problem

You are given an integer N. You have to find the minimum number of fibonacci terms required, that sums up to N.
Suppose you are given :

N = 14
so, the number of terms required would be 2, as 1+13, 8+5+1, 3+5+5+1 and many others can sum up to 14, but minimum number of terms required are 2.

N = 17
the answer would be 3, as 8+8+1, 13+2+2 and 8+3+3+3, all sum up to 17, but minimum number of terms required would be 3.

Approach

Well, if you notice here, we don't have any restriction on number of terms we can use to complete our sum N and as fibonacci series has 1 as a term we can make any sum we require by adding only 1. So the problem here is to minimise the number of terms used and not to find the combination of terms.
So, in these type of problems, where we need a minimum or maximum as our answer, Greedy Algorithm is mostly used. In Greedy algorithm we find find our solution step by step, choosing each step which is most beneficial to us.

In this problem also, we first create a fibonacci sequence till less than or equal to N and then start from end, checking each term which satisfies our requirements.
We started from end because, to complete the sum N in minimum terms we have to use the largest term available and completing the required sum.
Each time we use a term we increment our answer by 1 and return that in last.

Pseudocode

1. Create fibonacci sequence till less than or equal to N.
2. Initialise two variables : answer, j = 0 , last index of fib sequence.
3. Start a while loop whith condition N>0.
4. Increment answer variable by the number of times last term of fib sequence(fib[j]) is used(by dividing N by fib[j]).
5. Decrement j by 1.
6. Change N to our remaining sum required(N % fib[j]).
7. Let while loop to repeat till condition is not violated.
8. Return answer variable.

Implementation in Python

# Function to calculate Fibonacci Terms 
def fibonacci(fib, N): 

    fib.append(0) 
    fib.append(1) 
    fib.append(1) 
    
    # Calculate all Fibonacci terms which are less than or equal to K. 
    i = 3
    while True: 
        next = (fib[i - 1] + fib[i - 2]) 
        
        # Check if we reached N or not 
        if next > N: 
            return # Fibonacci sequence completed
        fib.append(next) 
        i+=1


# Function to find the minimum number of fibonacci terms having sum equal to N. 
def minimum(K): 

    # Making fibonacci sequence till less than or equal to N 
    fib = [] 
    fibonacci(fib, N) 
    
    answer, j = 0, len(fib) - 1
    
    # Subtract Fibonacci terms from N till N > 0.
    while N > 0:
        
        # Divide N by j-th Fibonacci term to find how many times this term is used
        answer += N / fib[j]
        N %= fib[j] 

        j -= 1
	
    return answer

# Example execution
N = 17
print(minimum(N))

Workflow of 'minimum' function

• Suppose we have N = 4. We generate the fibonacci sequence till less than or equal to 4. It means our fibonacci sequence generated would be : fib = [0,1,1,2,3]
• Then we start our while loop with j as index of last term in fib, means j = 4 and answer = 0.
• We first increment our answer by the number of times we can use the term at j index means answer += N // fib[j].
• Then we make our N as the remaining sum we need means N %= fib[j].
• Then we decrement our j by 1 : j -= 1
• This process is repeated till we have N > 0.

Complexity

Time Complexity: O(log N)

The time complexity is logN as we need to generate all fibonacci numbers less than N which is approximately logN and generating all will take logN time. Following this, processing all fibonacci numbers in a greedy way will take O(logN) time as well.

Space Complexity: O(log N)

The space complexity is O(log N) as we need to store the fibonacci numbers that are less than N.

Can you think of an alternative approach?

With this, you have the complete knowledge of solving this problem. Enjoy.