Equal Array

3.4

22 votes
Algorithms, Dynamic Programming, Easy
Problem

You are given an array A of size N

Find the minimum non negative number X such that there exist an index j and when you can replace Aj by Aj+X, the sum of elements of array from index 1 to j  and j+1 to  N becomes equal, where 1jN1. Assume array to be 1-indexed.

If there is no possible X print 1 in separate line.

Input Format

The first line contains T, the number of test cases.
For each Test case :
The first line contains an integer N, size of the array.
The second line contains N space-separated integers, the ith of which is Ai.

Input Constraints

1T105
2N105
0Ai106
Sum of N all over testcases doesn't not exceed 106.

Output Format

For each test case, print the required answer in separate line.

Sample Input
1
5
1 2 3 2 1
Sample Output
3
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Add 3 to the 2ndindex(1-indexing). 

Editor Image

?