## Friday, January 15, 2016

### Count Fibonacci numbers in given range in O(Log n) time and O(1) space - GeeksforGeeks

Count Fibonacci numbers in given range in O(Log n) time and O(1) space - GeeksforGeeks
Given a range, count Fibonacci numbers in given range. First few Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, ..

An Efficient Solution is to use previous Fibonacci Number to generate next using simple Fibonacci formula that fn = fn-1 + fn-2.
This looks simple solution, but many people got confused here as time complexity of this solution looks more.
`int` `countFibs(``int` `low, ``int` `high)`
`{`
`    ``// Initialize first three Fibonacci Numbers`
`    ``int` `f1 = 0, f2 = 1, f3 = 1;`

`    ``// Count fibonacci numbers in given range`
`    ``int` `result = 0;`

`    ``while` `(f1 <= high)`
`    ``{`
`        ``if` `(f1 >= low)`
`           ``result++;`
`        ``f1 = f2;`
`        ``f2 = f3;`
`        ``f3 = f1 + f2;`
`    ``}`

`    ``return` `result;`
`}`

Time Complexity Analysis:
Consider the that Fibonacci Numbers can be written as below
So the value of Fibonacci numbers grow exponentially. It means that the while loop grows exponentially till it reaches ‘high’. So the loop runs O(Log (high)) times.
One solution could be directly use above formula to find count of Fibonacci Numbers, but that is not practically feasible (See this for details).
Read full article from Count Fibonacci numbers in given range in O(Log n) time and O(1) space - GeeksforGeeks