Zero-sum array

★★★★★

3.8

12 votes

Applications of Dynamic Programming, Algorithms, Math, Dynamic Programming

Details

Submissions

Discussion

Editorial

Problem

You are given an array having $n$ elements. In one operation, you can make $a[i]=a[i]*(-1)$ , that is, you can change a positive number into a negative number and vice versa. You can use this operations for several times.

Your task is to print the minimum number of operations that are required to make the sum of elements of array zero.

Input format

The first line contains $t$ denoting the number of test cases. $1⩽t⩽10$
The first line of each test case contains $n$ denoting the size of the array. $0<n⩽10^{3}$
The second line of each test case contains $n$ denoting the elements of the array. $-10^{3}⩽a[i]⩽10^{3}$

Output format

In a new line, print the minimum number of operations that required to make the sum of elements zero. Otherwise, print $-1$ if you cannot make the sum of elements in array zero after applying many operations.

Note: The absoulte value of the sum of the elements of the array in input is not more than $10^3$ .

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

Explanation : 

First Test Case : 
2 operations required on elements 2 & 6. New array becomes = [-6,1,4,3,-2]. And the total sum = 0.

Second Test Case :

If operation is performed on 3 , new array becomes = [2,1,-3]. And total sum = 0. Thus, only 1 operation is required.