We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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!!
Fibonacci grows fast enough that all elements from 0 -> 10^10 is only about 50 entries. I just hashed entries from 0 up to the max val asked for and that worked for me.
Once you start caching, speed is never an issue. I just used an array for my look up table and even just doing a linear traversal of it, I was well under the time limit.
The thing about computing using that formula is that you're going to have to do floating-point calculations. This raises a couple of issues:
Can you easily estimate the amount of precision you're going to need to take a small number to a large number and have the rounding error be less than 0.5?
Is it even more efficient to use the closed form? Integer addition and modulo operations are faster than calculating exponentials and logarithms, and the extra storage space is neglible.
I checked Binet's formula and it's more elegant;however, since the max 10^10, the number of elements in array is 50, so just straight forward pre-computation should work too.
Is Fibo
You are viewing a single comment's thread. Return to all comments →
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!!
Fibonacci grows fast enough that all elements from 0 -> 10^10 is only about 50 entries. I just hashed entries from 0 up to the max val asked for and that worked for me.
Yeah memoization is the key.
Once you start caching, speed is never an issue. I just used an array for my look up table and even just doing a linear traversal of it, I was well under the time limit.
uh, read about the Binet formula, you can get n-th Fibonacci number in the closed form, no loops needed.
The thing about computing using that formula is that you're going to have to do floating-point calculations. This raises a couple of issues:
Can you easily estimate the amount of precision you're going to need to take a small number to a large number and have the rounding error be less than 0.5?
Is it even more efficient to use the closed form? Integer addition and modulo operations are faster than calculating exponentials and logarithms, and the extra storage space is neglible.
like daniel said, linear search of 50-element array would be way faster than doing the floating point computations needed for Binet formula.
Thanks, Your solution helped me. Seems "Binet's formula" has limitation in implementation wise.
Little trick, store the entries of fibonnacci numbers as a set, the lookup for a set is O(1) while for a list is O(n).
that's what I tried first too, wasn't sure why this problem is marked as medium difficulty. I created the first 30k fib numbers but only needed 50 lol
I checked Binet's formula and it's more elegant;however, since the max 10^10, the number of elements in array is 50, so just straight forward pre-computation should work too.
True.. check this out; string solve(long F) { double root5 = sqrt(5); double phi = (1 + root5) / 2; long nf = (long)(log(F*root5) / log(phi) + 0.5 ); long Fn = (long)( pow(phi, nf)/root5 + 0.5);
if (Fn==F) return "IsFibo"; else return "IsNotFibo"; }
or, you could just use Python and not worry about it.