Last Updated: 29 Apr, 2021
Fibonacci Sum
Moderate
Asked in companies
Given two integers, ‘N’ and ‘M’, your task is to find the sum of Fibonacci numbers between ‘fib(N)’ and ‘fib(M)’ where ‘fib(N)’ represents the Nth Fibonacci number and ‘fib(M)’ represents the Mth Fibonacci number. The sum is given by sum(N, M) = fib(N) + fib(N+1) + fib(N+2) … fib(M). Since the answer could be large, so you have to return the sum modulo 10^9 + 7.
The fibonacci relation is given by:
fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2), n >= 2, where fib(n) represents the nth fibonacci number.
Input format:
The first line of input contains an integer ‘T’, denoting the number of test cases.
The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, which denote the start and end of the range.
Output format:
For each test case, print the sum of Fibonacci numbers between ‘fib(N)’ and ‘fib(M)’.
Print the output for each test case in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 1000
0 <= N <= M <= 10^9
Where ‘T’ represents the number of test cases, and ‘N’ and ‘M’ represents the starting and ending of the range respectively.
Time Limit: 1 sec
Approaches
- The idea behind this approach is that we will find all the Fibonacci numbers from fib(N) to fib(M) using recursion and add them simultaneously.
- The recursive formula to find the Nth Fibonacci number is fib(N) = fib(N-1) + fib(N-2).
- The cumulative sum of all the Fibonacci numbers from fib(N) to fib(M) is our required result.
Algorithm:
- Create a variable sum initialized to 0.
- Now for each value, i from N to M perform the following steps:
- Find the ith Fibonacci number using recursion by calling the function fibonacciNumbers(int x) and store it in a variable temp.
- Update sum as (sum + temp)%1000000007.
- Inside the fibonacciNumbers(int x) function:
- If x is less than or equal to 1, then we will return x from the function
- Otherwise, we will return fibonacciNumbers(x-1) + fibonacciNumbers(x-2).
- Finally, return the sum which is our required answer.
- The idea behind this approach is that we will find all the Fibonacci numbers till fib(M) and store them in an array fib.
- Then iterate over array fib from i = N to i = M and calculate the sum by adding all the Fibonacci numbers between N and M.
- The cumulative sum is our required result.
Algorithm:
- Create an array fib of size M.
- Now initialize fib[0] = 0 and fib[1] = 1.
- Now iterate from i = 2 to i = M and update fib[i] as fib[i-1] + fib[i-2].
- Create a variable sum initialized to 0.
- Then iterate through array fib from i = N to i = M and update sum as (sum + fib[i])%1000000007.
- Finally, return the sum which is our required answer.
- Since the relation is fib(N) = fib(N-1) + fib(N-2). We can rewrite this relation is
- fib(N-1) = fib(N+1) - fib(N)
- fib(N-2) = fib(N) - fib(N-1)
- …
- fib(0) = fib(2) - fib(1)
- So if we add all above equations then
- fib(N-1) + fib(N-2) + fib(N-3) … + fib(0) = fib(N+1) - fib(1) = sum(N-1)
- sum(N-1) = fib(N+1) - 1 => sum(N) = fib(N+2) - 1.
- Since sum till Nth fibonacci numbers is given by: sum(N) = fib(N+2) - 1. So, sum(N, M) = sum(M) - sum(N-1) => fib(M+2) - 1 - (fib(N+1) - 1) => fib(M+2) - fib(N+1).
- Now we have to compute sum(N, M) = fib(M+2) - fib(N+1).
- Fibonacci numbers can also be calculated using Binet’s formula but due to precision issues, it is not recommended to calculate Fibonacci numbers using this formula.
- Since the Nth term of fibonacci sequence is given by fib(N) = fib(N-1) + fib(N-2) and base conditions are fib(0) = 0 and fib(1) = 1.
- So if you try to represent the above relation in a form matrix then:
- So if we want to get a 2X1 matrix of [fib(N), fib(N-1)] we have to multiply a 2X2 matrix [[1, 1] , [1, 0]] with a 2X1 matrix [fib(N-1) , fib(N-2)].
- [fib(N), fib(N-1)] = [[1, 1] , [1, 0]] * [fib(N-1) , fib(N-2)].
- The Nth term of the sequence is extracted from the first row of the resultant matrix.
- So the Nth term of a Fibonacci sequence is given in the first row. But to generalize the above formula to find the Nth term of Fibonacci sequence with base conditions it will be rewritten as:
- [fib(N), fib(N-1)] = [[1, 1] , [1, 0]] ^ (N-1)* [fib(1) , fib(0)]
- [[1, 1] , [1, 0]] ^ (N-1) can be calculated with the help of matrix exponentiation.
- Basically, we have to compute fib(M+2) and fib(N+1) using the above method, which will give our required answer where fib(M+2) represents the (M+2)th Fibonacci number and fib(N+1) represents the (N+1)th Fibonacci number.
Algorithm:
- Create a function compute(int K) and call it first to compute (M+2)th Fibonacci number and then call it again to compute (N+1)th Fibonacci number.
- Inside the function compute(int K) perform the following:
- We will first create a 2D array transform and initialize it as [[1, 1], [1, 0]].
- Also, create an array helper and initialize it as {1, 0}.
- Now update array transform as power(transform, K-1) using binary exponentiation method.
- Create a variable ans initialized to 0.
- Now run a loop on helper array from i = 0 to i = 1 and for each value of helper update ans as (ans + transform[0][i]*helper[i])%1000000007.
- Now return the value of ans.
- Finally when we get both values i.e compute(M+2) and compute(N+1) simply return the answer as compute(M%+2) - compute(N+1).
Similar problems
Pair Product Div by K
Moderate
Posted: 15 May, 2022
Pair Product Div by K
Moderate
Posted: 15 May, 2022
Merge Two Sorted Arrays Without Extra Space
Moderate
Posted: 19 Nov, 2022
Merge Two Sorted Arrays Without Extra Space
Moderate
Posted: 19 Nov, 2022
Co-Prime
Hard
Posted: 14 Dec, 2022
First Digit One
Moderate
Posted: 14 Oct, 2025
Special Digit Numbers
Hard
Posted: 31 Oct, 2025