PROBLEM LINK:
Author: Vineet Paliwal
Tester: Roman Rubanenko
Editorialist: Jingbo Shang
DIFFICULTY:
Easy
PREREQUISITES:
Fibonacci Property, Quick Sort, Offline Algorithm, Hash, Binary Search
PROBLEM:
Given T big integers with at most D digits, determine whether it can be a fibonacci number. The total digits are L.
EXPLANATION:
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.