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.
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) .
search on google