http://stackoverflow.com/questions/5927215/fibonacci-series-between-two-numbers
If
(5*N*N + 4) or (5*N*N - 4) for a given N >= 0 is a perfect square then the number is Fibonacci. Employ this method to generate Fibonacci series between two numbers.
i have a solution which works in O(log K log K) .
the idea is the fibonacci series is monotonic (i.e . fib(i)<= fib(i+1)) .
using this fact we can do binary search and find the index of the greatest fibonacci number which is not greater than B (smaller or equal to B) lets call this e , and find the index of the smallest fibonacci number which is greater than or equal to A , let's call it s .
the answer is (e-s+1).
the idea is the fibonacci series is monotonic (i.e . fib(i)<= fib(i+1)) .
using this fact we can do binary search and find the index of the greatest fibonacci number which is not greater than B (smaller or equal to B) lets call this e , and find the index of the smallest fibonacci number which is greater than or equal to A , let's call it s .
the answer is (e-s+1).
you can calculate any fibonacci number in log N where N is the index of the number using matrix power or any other formula .
so the total complexity is O(log K log K ) .
so the total complexity is O(log K log K ) .
