@bittu: yes, this can be the way. just make ur fib generator faster(using
matrix expo.) for less complexity.
On Tue, May 24, 2011 at 7:33 AM, bittu <shashank7andr...@gmail.com> wrote:
> @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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
-Aakash Johari
(IIIT Allahabad)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
