The Lost Arithmetic Sequences
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Jem couldn't even finish half of the homework exercises in "Advanced topics in algorithm" class. The teacher is really upset and gives him one final problem to solve - if he can't solve it, he is gonna fail the course.
Jem is given an array A consisting of N integers. The teacher asks him to remove exactly one number in the array to make the array become an arithmetic progressions.
Jem wanted to ask the teacher about the definition of arithmetic progressions but he remembered that he had heard this term in last week's lesson just before falling asleep. Now his life is in your hands again!
Anyways, we provide you the definition of arithmetic progression. Arithmetic progression is a sequence of numbers, where the difference between any two adjacent numbers is same.
Input contains mutilpe test cases. The first line of the input contains a single integer T represents the number of tests. It is followed by T group of line represent the test cases.
Each test case consists of two lines where the first line contains a single integer N.
The second line contains N space separated integers denoting the array A.
For each test case print out single integer which is the number you will remove from the array. If there is more than one solution take the smallest one. If there is no solution print out -1.
- 1 ≤ T ≤ 10
- 2 ≤ N ≤ 105
- 0 ≤ Ai ≤ 109
Input: 3 2 3 4 4 1 5 3 4 6 2 4 6 7 8 10 Output: 3 -1 7
test 1: an array contain a single integer is considered to be an arithmetic progression so you can remove any number in the array. But note that we must print out the smallest result which is 3.
test 2: there is no solution since none of [1, 3, 4], [1, 5, 3], [1, 5, 4], [5, 3, 4] is an arithmetic progressions.
test 3: the only way to archive an airthmetic progressions is remove the number 7 which will give us [2, 4, 6, 8, 10].
|Tags||cook74, dynamic-programming, easy, tuananh93|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.