# CMC304 - Editorial

Binary Mess

Author: artha6391
Tester: anushka_nagar
Editorialist: anushka_nagar

EASY

# PROBLEM:

Select only a single integer from the given integer array and increment or decrement it by one to make the XOR-SUM minimum.

# QUICK EXPLANATION:

Since we know XOR of a number with itself is 0, hence the best way is to select an integer (A[i]), excluding whom the rest of integers have a XOR-SUM (x), such that number of operations (|x – A[i]|) is minimum.

# EXPLANATION:

Bitwise XOR operation: Takes two numbers as operands and does XOR on every bit of two numbers. The result of XOR is 1 if the two bits are different.

XOR SUM: XOR-SUM refers to successive XOR operations on integers. Suppose you have numbers 1,5,2,3,6,7 and you have to find their XOR-SUM then, XOR-SUM will be 1^5^2^3^6^7 = 4.

Properties of XOR

1. Commutative
2. Associative
3. a^a = 0
4. 0^a = a

we can calculate the XOR-SUM of all integers in the array A[n], let’s call it S. To find the XOR-SUM of integers except the selected A[i], we can perform S^A[i] = x. And then we’ll calculate number of operations as |x – A[i]| which will make A[i] equal to x, and XOR-SUM will be minimum i.e., 0.

This solution will take O(N) time.

# SOLUTIONS:

Setter's Solution
``````#include<iostream>
#include<algorithm>
#include<vector>
#include<climits>
using namespace std;

int main()
{
int t;
cin>>t;

while(t--)
{
long long int n, small, i, sum, x;
cin>>n;
small = LLONG_MAX;
long long int v[n];
sum = 0;
for(i=0;i<n;i++){
cin>>v[i];
sum ^= v[i];
}
for(i=0;i<n;i++)
{
x = sum^v[i];
small= min( small, abs(x-v[i]) );
}
cout<<small<<endl;
}
return 0;
}
``````
Tester's Solution
``````#include<iostream>
#include<algorithm>
#include<vector>
#include<climits>
using namespace std;

int main()
{
int t;
cin>>t;

while(t--)
{
long long int n, small, i, sum, x;
cin>>n;
small = LLONG_MAX;
long long int v[n];
sum = 0;
for(i=0;i<n;i++){
cin>>v[i];
sum ^= v[i];
}
for(i=0;i<n;i++)
{
x = sum^v[i];
small= min( small, abs(x-v[i]) );
}
cout<<small<<endl;
}
return 0;
}
``````
Editorialist's Solution
``````#include<iostream>
#include<algorithm>
#include<vector>
#include<climits>
using namespace std;

int main()
{
int t;
cin>>t;

while(t--)
{
long long int n, small, i, sum, x;
cin>>n;
small = LLONG_MAX;
long long int v[n];
sum = 0;
for(i=0;i<n;i++){
cin>>v[i];
sum ^= v[i];
}
for(i=0;i<n;i++)
{
x = sum^v[i];
small= min( small, abs(x-v[i]) );
}
cout<<small<<endl;
}
return 0;
}
``````