Author: Vineet Paliwal
Tester: Roman Rubanenko
Editorialist: Jingbo Shang
Fibonacci Property, Quick Sort, Offline Algorithm, Hash, Binary Search
Given T big integers with at most D digits, determine whether it can be a fibonacci number. The total digits are L.
There are a number of ways to solve this problem.
If you look up fibonacci properties online, you may find the followings:
n is a fibonacci number if and only if 5 * n * n + 4 or 5 * n * n - 4 is a perfect square number.
Using this property, together with big integer multiplication and sqrt, you can get the answer.
However, this method is too complex to pass this problem. It is worth noting that fibonacci number increases exponentially. And thus, there are only O(D) fibonacci numbers have at most D digits. This observation gives us the intuition to solve this problem much simpler.
The fist method is an offline version. First, we load all queries and sorted them. This step will take O(TDlogT) if we use quick sort. Second, we compute fibonacci numbers one after another using big integer addition. For each fibonacci number, check its relationship with the current smallest query number:
If the they are same, then the answer of that query is YES and let’s look at the next query number;
If the fibonacci number is smaller, then let’s look at the next fibonacci number;
if the fibonacci number is larger, then the answer of that query is NO and let’s look at the next query number.
This procedure needs O((D + T)D) time. Therefore, this offline version’s time complexity is O(TDlogT + (D + T)D).
The second one involves hash. We can simply generate O(D) fibonacci number and only restore the remainder of some relatively big number, for example, 2^64 or 10^9+7. And then, check the query number’s remainder to see whether it occurred using hash table or tree set. Suppose we use hash table, the time complexity is O(D + L).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.