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.

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 :slight_smile: search on google

1 Like

thanks @kuruma

Hope it helped you :slight_smile:

use fib[1]+fib[2]+fib[3]…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[2][2]={{1,1},{1,0}};
long long transformation[2][2]={{1,1},{1,0}};
void matrixMul(long long a[2][2],long long b[2][2])
{
 int i,j,k;
 long long re[2][2] ={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[0][0]=result[0][1]=result[1][0]=1;
result[1][1]=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[0][0]-1;
}
initialize();
if(m == 0 || m == 1) {
		x=m;
}
else {
	power(m+1);
	y=result[0][0]-1;
}
if(x>y){
	x=x-y;
}
else
	x=y-x;

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