Geometric Sequence

View as PDF

Submit solution

Points: 10
Time limit: 0.6s
Memory limit: 64M

Problem type

A sequence of integers is called a geometric sequence if the ratio of consecutive numbers is constant.
For example, (3,6,12,24) is a geometric sequence (each term is equal to twice the previous number).

Now, with such a sequence, we will shuffle it around and remove some of the elements.
Given the result of such a transformation, try to recover the "geometric ratio" of the original sequence.

If there are multiple values, output the one with the greatest absolute value (if there's still a tie, output the positive one).
If there is no such sequence, output 0.

Input Specification

The number of integers, 2 \le N \le 100\,000.
N lines, each with one non-zero integer x (|x| \le 10^{18}).

Output Specification

The ratio of the original sequence (if one exists).
The relative error of the answer must be within 10^{-9}.

\displaystyle \frac{|\text{answer} - \text{expected}|}{|\text{expected}|} < 10^{-9}

Sample Input

3
1
3
27

Sample Output

3

The original sequence could have been 1,3,9,27 or 27,9,3,1; the former has the greater ratio.


Comments

There are no comments at the moment.