nth Fibonacci Number

I was in the test run of a programming contest just a couple of days back and there was this good old problem of finding out the nth Fibonacci Number. But the constraints were tight (upto 10^9) and the number of test cases were also high ( ~100). Well I knew that the conventional DP solution of O(n) won’t work, still I tried and got the TLE . Out of the shackles of laziness, I went out to code the O(log(n)) version of calculating the nth Fibonacci Number. The method to do it is very simple, the recurrence is

I used recursion and coded it. Interestingly, I got TLE again . When I ran the code on my system it was very slow for high values. Any Guesses why ??? Think it over
Anyways, I figured out immediately why it was slow and then used the good old technique of Memoization to code the same solution with slight modification. This time it got accepted
The code which I made.

#include<stdio.h>
#include<string.h>
typedef long long LL;

int mem[5000000];

LL fib(LL n) {
	if ( n == 1 )
		return 1;
	if ( n == 2 )
		return 1;
	if (n & 1 ) // odd 
	{
		LL t1, t2, t3;
		if ((n+1)/2 < 5000000 && mem[(n+1)/2] != 0 )
			t1 = mem[(n+1)/2];
		else {
			t1 = fib( (n + 1)/2)%10007;
			if ( (n+1)/2  < 5000000) 
				mem[(n+1)/2] = (int)t1;
		}
		if ((n+1)/2 - 1 < 5000000 && mem[(n+1)/2-1] != 0 )
			t2 = mem[(n+1)/2-1];
		else {
			t2 = fib( (n + 1)/2-1)%10007;
			if ( (n+1)/2 -1 < 5000000) 
				mem[(n+1)/2-1] = (int)t2;
		}
		return ((t1*t1)%10007 + (t2*t2)%10007)%10007;
	}
	else {
		LL t1, t2, t3;
		if ((n)/2 < 5000000 && mem[(n)/2] != 0 )
			t1 = mem[(n)/2];
		else {
			t1 = fib( (n )/2)%10007;
			if ( (n)/2  < 5000000) 
				mem[(n)/2] = (int)t1;
		}
		if ((n)/2 - 1 < 5000000 && mem[(n)/2-1] != 0 )
			t2 = mem[(n)/2-1];
		else {
			t2 = fib( (n)/2-1)%10007;
			if ( (n)/2 -1 < 5000000) 
				mem[(n)/2-1] = (int)t2;
		}
		if ((n)/2 + 1 < 5000000 && mem[(n)/2+1] != 0 )
			t3 = mem[(n)/2+1];
		else {
			t3 = fib( (n)/2+1)%10007;
			if ( (n)/2 +1 < 5000000) 
				mem[(n)/2+1] = (int)t3;
		}
		return (((t2 + t3)%10007)*t1)%10007;
	}
}

int main()
{
	int t;
	memset((void *)mem,0,5000000*sizeof(int));
	long long int n;
	scanf("%d",&t);
	while (t--) {
		scanf("%lld",&n);
		if ( n == 1) { printf("1\n"); continue;}
		if ( n == 2) { printf("2\n"); continue;}
		printf("%lld\n",fib(n+1));
	}
	return 0;
}

It was good that I coded it, because nowadays people are not satisfied with the good old O(n) DP method . They want the O(log(n)) code. I remember a company at our campus asked a guy to do it, the interviewer helped him a lot but he couldn’t answer it. Nice practice to do actually