All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Equal Array
Tag(s):

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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Dell-EMC

Challenge Name

Dell Developer Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?