Fibonacci Sum

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
33 upvotes
Asked in companies
WalmartNatwest GroupMathworks

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
2 6
0 5
Sample Output 1:
19
12
Explanation 1:
For the first test case, 
The Fibonacci numbers between fib(2) and fib(6) are {1, 2, 3, 5, 8}. Their sum is equal to 19. Hence the output is 19.

For the second test case,
The Fibonacci numbers between fib(0) and fib(5) are {0, 1, 1, 2, 3, 5}. Their sum is equal to 12. Hence the output is 12.
Sample Input 2:
2
3 6
6 7
Sample Output 2:
18
21
Hint

Find all the Fibonacci numbers recursively and add them.

Approaches (3)
Recursive Approach

 

  • 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.
Time Complexity

O(M*2^M), where ‘N’ and ‘M’ represent the start and the end of the range.

 

Since we are using a recursive function fibonacciNumbers() to calculate Fibonacci numbers from fib(N) to fib(M) which takes O(M*2^M) time. So overall time complexity will be O(M*2^M). 

Space Complexity

O(M), where ‘N’ and ‘M’ represent the start and the end of the range

 

Since we are using a recursive function and in the worst case, there can be O(M) states in the recursion stack. So, the overall space complexity will be O(M). 

Code Solution
(100% EXP penalty)
Fibonacci Sum
Full screen
Console