Can any one help me to understand test cases 5 to 9. For me all are failing. I tried different values but all passed. Not able to think any conner cases that can fail.

This problem was an eye opener. If you are not connected to your basics about int , long int and how to find a fibnonaci number using "Binet's formula", then you are in trouble in bigger testcases. Also boundry conditions do play an important part. Nice problem!!

A number is Fibonacci if and only if one or both of (5*n2 + 4) or (5*n2 – 4) is a perfect square

I had insane reason for failing test cases. Output was saying "terminated due to timeout". That is legit error. But the reason was because i declared some variables with var keyword (C#).

After changing that from "var" to "long" I passed the tests! This has nothing to do with real life since using var keywords does not have performance hits for the code.

Solved it by using Binet's formular and fast doubling. This approach is more memory effecient than memorising the entire Fibonacci sequence in your data structure. Speed-wise I am getting an average of 0.14 sec for all test cases in C.