Problem
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 ��Ai and ��Aj as ��⊕��Ai⊕Aj, 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−1.
Input Format
- 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 Format
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−1.
Constraints
- 1≤�≤7001≤T≤700
- 1≤�≤1051≤N≤105
- 0≤��≤10≤Ai≤1
- The sum of �N over all test cases does not exceed 2⋅1052⋅105.
Sample 1:
Input
Output
3 1 0 2 1 0 4 1 0 0 0
-1 0 1
Explanation:
Test case 11: It is not possible to make the array good using any number of operations.
Test case 22: The number of ones as well as zeros is 11. Since the array is already good, we do not need to apply any operation.
Test case 33: The number of ones is 11 and the number of zeros is 33. We perform the following operation:
- Select �=1i=1 and �=3j=3, and set �1A1 and �3A3 as �1⊕�3=1⊕0=1A1⊕A3=1⊕0=1. Thus, array becomes [1,0,1,0][1,0,1,0].
The array has equal number of zeros and ones now. Thus, the array is good.
