 # Fibonacci sum problem

Question->http://www.spoj.com/problems/FIBOSUM/ Basically question is to find the sum
of fibonacci numbers starting from N to M I did this question using the factor (1+sqrt(5))/2.I >found N,N+1 using this factor by O(log N) multiplication.Then finally i traversed all the numbers >from N+2 to M and side by side adding their sum.My code takes O(N-M+logN) time.But i am getting >time limit exceeded on this solution.What can i do to improve the time complexity of my solution.I
thought of doing using dynamic programming will it be faster ??plz help

``````#include<iostream>
#include<math.h>
long int power_multiply(long int,long int&);
using namespace std;
int main()
{
long int N,M,a,b,sum=0,c,t;
cin>>t;
while(t--){
cin>>N>>M;
a=power_multiply(N,b);//i passed b as reference so that a=f(n),b=f(n+1) are simultaneously
if(N==M){sum=a;}      //calculated
else
{  sum=a+b;
long int i=N+2;
while(i!=M+1)
{
c=b+a;
sum=sum+c;
sum%=1000000007;
a=b;
b=c;
i++;
}
}}//else
cout<<sum<<"\n";
}
return 0;
}
long int power_multiply(long int a,long int &b)//this mulitplication takes O(logN) time
{
double x=(1+sqrt(5))/2,ans=1,y=x;
while(a>0)
{
if(a%2!=0)
{
ans=ans*x;
}
x=x*x;
a=a/2;
}
a=floor(ans/sqrt(5)+0.5);   //for finally converting a to its nearest integer

b=floor((ans*y)/sqrt(5)+0.5);   //for computing b from answer which i got while
//evaluating 'a' and also converting it to its
//nearest integer
return a;
}``````

Your time complexity is too large. I don’t want to give too much away, but think about the case when M=0. Can you solve this simplified version of the problem in faster than O(N) time?

EDIT: I mixed up N and M. I mean think about the problem when N=0, and you want to solve this faster than O(M) time.

@lg5293 In anycase we have to find first fib(N) and i have found it in O(logN) time,i don’t think there is any better method of finding fib(N) which could find it in less than O(logN) correct me if i m wrong.Then after that we have to traverse N+1 to M to calculate each fibonacci from previous 2 numbers.Also i founded fib(N+1) using the result obtained from fib(N).Between thanks for the boundary case when M=0 i have improved the code to deal with that case.But i m still not able to work with that complexity part.

use fib+fib+fib…fib[n]=fib[n+2]-1

Check my code Getting Wrong Answer
For Fibosum ON SPOJ.
https://www.spoj.com/problems/FIBOSUM/question

``````#include <bits/stdc++.h>
using namespace std;

#define mod 1000000007

long long result={{1,1},{1,0}};
long long transformation={{1,1},{1,0}};
void matrixMul(long long a,long long b)
{
int i,j,k;
long long re ={0};
for(i=0;i<2;i++) {
for(j=0;j<2;j++) {
for(k=0;k<2;k++) {
re[i][j] = (re[i][j] + (a[i][k]*b[k][j])%mod ) % mod;
}
}
}
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
result[i][j]=re[i][j];
}
}

void initialize() {
result=result=result=1;
result=0;
}
void power(int n)
{
if(n==1)
return ;
power(n/2);
matrixMul(result,result);
if(n&1)
{
matrixMul(result,transformation);
}
}

int main()
{
int t;
cin>>t;
while(t--){
initialize();
long long n,m;
cin>>n>>m;
long long x,y;
if(n == 0 || n == 1) {
x=n;
}
else {
power(n);
x=result-1;
}
initialize();
if(m == 0 || m == 1) {
x=m;
}
else {
power(m+1);
y=result-1;
}
if(x>y){
x=x-y;
}
else
x=y-x;

cout<<((x+mod)%mod)<<endl;
}
return 0;
}
``````

Oh, sorry I meant N=0, not M=0. I got the bounds messed up. Think about how you can compute that in faster than O(M) time.

I am not able to compute N to M faster than O(N-M) i tried matrix method too but it still giving time limit exceeded.I don’t know how can it be computed in less than O(N-M) because in anycase we have to traverse the whole N to M. Even the dynamic programming solution will take O(N-M) .

there’s a very elegant formula which you can use search on google

1 Like

thanks @kuruma

Hope it helped you 