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 :P. 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
Fibonacci Number - I
Fibonacci Number - II

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 :P. 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 🙂

Advertisements

About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: