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 of size . He wants to make the array good using the following type of operation:
- Select two indices and and set both and as , 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 .
Input Format
- The first line of input will contain a single integer , 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 , the size of the array.
- The second line contains space-separated integers, denoting the array .
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 .
Constraints
- The sum of over all test cases does not exceed .
Sample 1:
3 1 0 2 1 0 4 1 0 0 0
-1 0 1
Explanation:
Test case : It is not possible to make the array good using any number of operations.
Test case : The number of ones as well as zeros is . Since the array is already good, we do not need to apply any operation.
Test case : The number of ones is and the number of zeros is . We perform the following operation:
- Select and , and set and as . Thus, array becomes .
The array has equal number of zeros and ones now. Thus, the array is good.
Solution :
Cases:
zero here is the count of 0 and one here is the count of 1
1: if n is the odd answer is -1
2: if zero ==n then the answer is -1 as we cannot create any one.
3: n is 2 and one ==2 then we can create either 2 zero or 2 one
4: if one == zero then answer is 0
5: if zero is greater than one then we can XOR 1 and 0 to get two ones. so total moves needed is (zero-one)/2
6: if one is greater than zero then we can XOR two 1 and get two 0, so difference decreases by 4.
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.