Good XOR | Starters 81 Codechef | Solution C++

 

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 $�$ $(�\mathrm{\ne }�)$ and set both ${�}_{�}$ and ${�}_{�}$ as ${�}_{�}\oplus {�}_{�}$, where $\oplus$ 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 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 $-1$.

Constraints

• $1\le �\le 700$
• $1\le �\le 10^5$
• $0\le {�}_{�}\le 1$
• The sum of $�$ over all test cases does not exceed $2\cdot 10^5$.

Sample 1:

Input

Output

3
1
0
2
1 0
4
1 0 0 0

-1
0
1

Explanation:

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 $�=1$ and $�=3$, and set ${�}_1$ and ${�}_3$ as ${�}_1\oplus {�}_3=1\oplus 0=1$. Thus, array becomes $[1,0,1,0]$.

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.

void solve() {

int n;

cin>>n;

vi v(n);

int zero=0,one=0;

for (int i = 0; i < n; i++)

{

    cin>>v[i];

    v[i] == 1 ? ++one : ++zero;

}

if(one == zero) {

    cout<<0<<endl;

    return;

}

else if( zero==n || n%2==1 || (n==2 && one==2)){

    cout<<-1<<endl;

    return;

}

if(one<zero){

    cout<<(zero-one)/2<<endl;

}

else{

    int diff = abs(zero-one);

    if(diff%4==0){

        cout<<diff/4<<endl;

    }

    else if(diff%2==0){

        cout<<(diff/4)+2<<endl;

    }

}

}