All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Equal Array
/

Algorithms, Dynamic Programming

Problem
Editorial
Analytics

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 \(A_j\) by \(A_j+X\), the sum of elements of array from index \(1 \) to \(j\)  and \(j+1\) to  \(N\) becomes equal, where \(1 \le j \le N-1\). 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 \(i^{th}\) of which is \(A_i\).

Input Constraints

\( 1 \le T \le 10^{ 5} \)
\( 2 \le N \le 10^{5} \)
\( 0 \le A_i \le 10^{6} \)
Sum of N all over testcases doesn't not exceed \(10^{6}\).

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
Explanation

Add \(3\) to the \(2^{nd}\)index(1-indexing). 

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?