@Aakash Sir...can u clarify giving some examples....like i give input
N=10,it should O/P 8....if N=51,O/P=34
On 5/24/11, Aakash Johari <aakashj....@gmail.com> wrote:
> @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.
>
>
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=100000655377926 *
--
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.
