HCL America Interview Question
Software Engineer / DevelopersFirst 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)
This can be made fast if you use this property of Fibonacci numbers:
- LOLer August 20, 2009A number F is fibonacci if and only if one of 5F^2+4 or 5F^2-4 is is a perfect square.