BETXOR - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Mann Mehta

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Greedy, XOR Properties, Basic Math, Optimization, Observations

PROBLEM:

Given an algorithm you task is to optimize this in O(N).

function betterXOR ( array A [ ] , N ) {
    ans = 0
    for ( i = 0 ; i < N ; i = i + 1 ) {
        for ( j = i + 1 ; j < N ; j = j + 1 ) {
            ans = ans ^ A [ i ]  ^ A [ j ]  
          }
    }
    return ans  
}

QUICK EXPLANATION:

To optimize this O(N^2) function in to O(N) we will use the fundamental property of

XOR operation.

Property - 1 : - A ^ A = 0.
Property - 2 : - A ^ 0 = A.

Where ‘^’ denotes the XOR operation.

When N is even the output of function is same as xor of all elements.
When N is odd the output of function is 0.

EXPLANATION:

Let discussed this in detail by taking some example.

Before we begin the solution of this problem is completely depend on this two properties of XOR.

Property - 1 : - A ^ A = 0.
Property - 2 : - A ^ 0 = A.

Array [4] = { a_1 , a_2, a_3 , a_4 }

According to O(N^2) function we create the equation of the total XOR sum.

ans = 0

After iteration - 1

ans = (a_1^ a_2) ^ (a_1^ a_3) ^ (a_1^ a_4)

After iteration - 2

ans = (a_1 ^ a_2) ^ (a_1 ^ a_3) ^ (a_1 ^ a_4) ^ (a_2 ^ a_3) ^ (a_2 ^ a_4)

After iteration - 3

ans = (a_1 ^ a_2) ^ (a_1 ^ a_3) ^ (a_1 ^ a_4) ^ (a_2 ^ a_3) ^ (a_2 ^ a_4) ^ (a_3 ^ a_4)

Just rearranging the order to visualize the equation in better way.

ans = (a_1 ^ a_1 ^ a_1) ^ (a_2 ^ a_2 ^ a_2) ^ (a_3 ^ a_3 ^ a_3) ^ (a_4 ^ a_4 ^ a_4)

Now applying the first property of XOR.

ans = (0 ^ a_1) ^ (0 ^ a_2) ^ (0 ^ a_3) ^ (0 ^ a_4)

Now applying the second property of XOR.

ans =(a_1) ^ (a_2) ^ (a_3) ^ (a_4)

Observations

a_1 repeats exactly 3 times .
a_2 repeats exactly 3 times .
a_3 repeats exactly 3 times .
a_4 repeats exactly 3 times .

In general the repetition is exactly N-1 times.

Now if you carefully observe the final equation in terms of variable you notice that for
N = 4 all elements of the array repeats exactly (N-1) times.

So here in this example each element except its single occurrence, all other elements will give XOR sum as 0 using the 2^{nd} property of XOR and in the end only single element remains. Hence Instead using two loops we can generate the same output using single loop by XOR summing all elements.

If N is odd then N-1 is even at that time all elements repeats exactly even time hence the XOR sum will always lead to 0 using the first property of XOR.

When N is even the output of function is same as xor of all elements.
When N is odd the output of function is 0.

SOLUTIONS:

Setter's Solution 
///@author mann2108
///ILLUMINATI Season 5.
///Problem : BetterXOR

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t;
    cin>>t;
    while(t--){
        ll n,ans=0;
        cin>>n;
        ll a[n];
        for(ll i=0;i<n;i++)cin>>a[i];
        if(n%2==0)for(ll i=0;i<n;i++)ans^=a[i];
        cout<<ans<<endl;
    }
}