CareerCup

This can be made fast if you use this property of Fibonacci numbers:

A number F is fibonacci if and only if one of 5F^2+4 or 5F^2-4 is is a perfect square.

the first response is understood but dint get the binary search technique. Please explain in detail.

@kanp & lickie
By binary search he might be referring to check/look for the given number by doing binary search on a Fibonacci list, assuming we've this list at our disposal, right @ LOLer ? but i guess we dont have the list(partial) to make use of this technique.

First notice that fibonacci numbers form a increasing sequence.

Now, suppose you are given a number F.

You guess an n and calculate the nth fibonacci number, fib(n).

If F < fib(n), reduce the value of n in the standard binary search way
if F > fib(n), increase the value of n in the standard binary search way.

fib(n) can be calculated in O(log n) time using the matrix method.

So if F was such that fib(k) <= F < fib(k+1), you take O(log k) calls to the calculation of a fibonacci number to determine if F is fibonacci.

Thus O(log k) calls to calculate fibonacci, each being O(logk).
Thus the total time complexity is O(log^2 k).

Also, k = O(log F).

Thus time complexity if O( log(log F) * log (log F))

The normal 5F^2 +/- 4 perfect square detection algorithm probably takes O(log F) time. Smarter algorithms for detecting if 5F^2 +/- 4 is a perfect square probably end up calculating Fibonacci-type* numbers anyway...


(Fibonacci-type = numbers which can be calculated using the matrix method, for lack of a better word)