CareerCup

how can a better solution be a loop one.. I think Memoization is better ...!! wat say

there is a O(log n) algorithm using matrix multiplication.

def fun(n,memoryDict={}):
          if n == 1:
             return 1
          if n == 2:
             return 1
          if n-1 not in memoryDict and n-2 not in memoryDict:
             return fun(n-1,memoryDict) + fun(n-2,memoryDict)
          elif n-1 in memoryDict and n-2 not in memoryDict:
             return memoryDict[n-1] + fun(n-2,memoryDict)
          elif n-1 not in memoryDict and n-2 in memoryDict:
             return fun(n-1,memoryDict) + memoryDict[n-1]
          else:
             return memoryDict[n-1] + memoryDict[n-2]
#done

fib(2n) = fib(n+1)*fib(n) + fib(n)*fib(n-1)
= fib(n)*(fib(n+1)+fib(n-1))
= fib(n)*(fib(n)+2*fib(n-1))

fib(2n-1) = fib(n)^2 + fib(n-1)^2

// prints the nth fibonacci number based on the input valuye of n



# include<stdio.h>
# include<conio.h>
void main()
{
int a=0,b=1,c=0,n;
clrscr();
printf("Enter the number of fibonacci series\n");
scanf("%d",&n);
while(1)
{
if(c==n)
{
printf("%d",a);
break;
}
a=a+b;
b=a-b;
c++;
}
getch();
}