CMC304 - Editorial

editorial
, ,
1

PROBLEM LINK:

Binary Mess

Author: artha6391
Tester: anushka_nagar
Editorialist: anushka_nagar

DIFFICULTY:

EASY

PREREQUISITES:

XOR
XOR-SUM

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;
}