@all geeks
I have already posted it 2-3 forums..here let me post it again its
O(n) but the basic idea is clear if got the problem stmt correct then
we have to find out the largest Fibonacci number that is small then
given number n so say if n=10 then should be 8
for n=13 i=8
n=14 i=13 similarly for all n>13 & n <21 i will 13 & so on i don't why
so confusion ?? It Will Cover All Test Cases
#include<stdio.h>
int fib(int n)
{
int final=0,i,c,a=0,b=1;
for(i=2;i<n;i++)
{
c=a+b;
a=b;
b=c;
if(c<n)
final=c;
}
return final;
}
int main()
{
int n=14;
printf( " %d ", fib(n));
}
TC O(n)
SC O(1)
Run Here https://ideone.com/aCli7
Optimization: To get the answer in O(logn) we can use matrix
representation of Fibonacci number check wiki..& if you wants O(logn)
then i can also post that..I hope m clear ..There are already 6 Way
Known to me to find nth Fibonacci Number
only thing necessary is that optmization .. Correct me if anything
wrong ???
Thanks
Shashank>>" the Best Way To Escape From The problem is To Solve It"
CSE,BIT Mesra
Reach Me +91-9739002481
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
