Problem7998--CodeChef ASFA - Good XOR

7998: CodeChef ASFA - Good XOR

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitSolved: 1Submit Num: 1StatisticsShowOff!

Description

An binary array is called good, if the count of ones in the array is equal to the count of zeros.
Chef has a binary array A of size N. He wants to make the array good using the following type of operation:
  • Select two indices i and j (i=j) and set both $A_i$ and $A_j$ as $A_i⊕A_j$, where ⊕ denotes the bitwise XOR operation.
Determine the minimum number of operations required to make the array good. If it is not possible to make the array good using any number of operations, print −1.

Input

The first line of input will contain a single integer T, denoting the number of test cases.
Each test case consists of two lines of input.
  • The first line of each test case contains an integer N, the size of the array.
  • The second line contains N space-separated integers, denoting the array A.

Output

For each test case, output on a new line, the minimum number of operations required to make the array good. If it is not possible to make the array good using any number of operations, print −1.

Constraints

1≤T≤700
$1≤N≤10^5$
$0≤A_i≤1$
The sum of N over all test cases does not exceed $2⋅10^5$.

Sample 1 Input 

3
1
0
2
1 0
4
1 0 0 0

Sample 1 Output 

-1
0
1
Test case 1: It is not possible to make the array good using any number of operations.
Test case 2: The number of ones as well as zeros is 1. Since the array is already good, we do not need to apply any operation.
Test case 3: The number of ones is 1 and the number of zeros is 3. We perform the following operation:
  • Select i=1 and j=3, and set $A_1$ and $A_3$ as $A_1⊕A_3=1⊕0=1$. Thus, array becomes [1,0,1,0].
The array has equal number of zeros and ones now. Thus, the array is good.

Sample 2 Input 

1
2
1 1

Sample 2 Output 

-1

Sample 3 Input 

3
6
1 1 1 1 1 0
8
1 1 1 0 0 0 0 0
10
1 1 1 1 1 1 1 1 1 1

Sample 3 Output 

1
1
4

HINT

相同题目：CodeChef ASFA。

Source/Category

 
Submit