@ps: no, suppose for given N testcases, get the maximum one, and generate
fibs greater than that. and then for others u can get with binary search
only,
u will have to improve the fib generator, so basically matrix expo, can
help. other way of doing this is described in above post.
On Tue, May 24, 2011 at 6:52 AM, anshu mishra <anshumishra6...@gmail.com>wrote:
> @all
>
> it is simple binary search problem
>
> we can write
>
> f(n) = f(n/2 + 2)*f(n/2) + {f(n/2 + 1)}^2 if n is even similary u can get
> formula when n is odd.
>
> f(3), f(4), f(5) ----> f(6)
> f(6), f(7), f(8) ----> f(12)
> .
> .
> .
> as soon as you got a fibnocci number greater than n suppose p-- than you
> have two ranges p, p/2;
>
> now apply binary search in range (p/2 & p)
>
> that is cal f(p+p/2) compare the value from n. accordigly move left or
> right.
>
> till (p - p/2 != 1)
>
> solution is o(log(n));
>
> hopefully i am clear.
>
> --
> 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.
