# A XOR operation

this question asked in one of the previous Hackerearth contest .but i am unable to solve this problem during contest .Also editorial provided by hackerearth does not include any proof .

If any one can provide proof of logic how this logic working ?
You are given a set S of distinct positive integers of size n (n is always even). Print the minimum positive integer k that is greater than 0 such that after replacing each element e of the set S with e⊕k, set S remains the same.

Print -1if there is no such k.

Note: It is guaranteed that n/2 is odd.

Input format

• The first line contains a single integer t (1≤t≤100) denoting the number of test cases.
• The first line of each test case contains a single integer n (2≤n≤1e5) denoting the number of elements in the set.
• The second line of each test case contains n integers e (1≤e≤1e9).

Output format

Print t lines each containing a single line that contains k.

Input
1
6
5 6 9 10 13 14

Output
3

Lets say the Set be S:(e1,e2,e3.....,en)

• Find Xor for all set i.e P = `(e1^e2^e3...^en)`
• Now loop from first element to last element and inside every iteration find
x = arr[i]xorP
insert this x in the set S. if size of set changes then answer is not possible return -1 else continue.
• So if after iterating the whole array above condition never printed -1, hence answer is possible and it is P only.
• TC of this would be O(nlogn)

Finally question boils down to one condition the answer can either be P or answer cannot be possible.

Below is the implementation of above approach, Note here that it may require some optimizations as Overall time-complexity is O(t*n*logn) i haven’t tested it

``````#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define test(t) ll t; cin >> t; while(t--)
set<ll> S;
void solve();

//---------------------------------------------
signed main()
{

#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt","w",stdout);
#endif
FASTIO
test(t)
{
solve();
}
}
/////////////////////////////////////////////////////////////////////////////////////////
void solve()
{
ll n; cin >> n;
ll arr[n];
ll Xor;
for(int i=0;i<n;i++)
{
cin >> arr[i];
S.insert(arr[i]);
if(i==0)
{
Xor = arr[i];
}
else
{
Xor=(Xor^arr[i]);
}
}
ll x;
for(int i=0;i<n;i++)
{
x = Xor^arr[i];
int size1 = S.size();
S.insert(x);
int size2 = S.size();
if(size1 != size2)
{
cout<<"-1\n";
return;
}
}
cout << Xor << "\n";
S.clear();
return;
}
``````
1 Like

can you explain how this logic working and how you think ,if can it would great help for me

1 Like

Lets say We have an array with three elements {a,b,c} and thier xor value (a^b^c) = X

• Lets create a set S which contains values S : { `a , b , c , a^X , b^X , c^X` }
• so `a^X` = `a^a^b^c` = `b^c`
• similary `b^X` = `b^a^b^c` = `a^c`
• finally `c^X` = `c^a^b^c` = `a^b`

S : ( a , b , c , a^b , b^c , c^a )

Now if my X == ( a^b^c )
and if we Find (X xor Si) = p
we will find that eventually all p will belong to S only.

Which takes us to a condition that set should should contain all possible xor subsets of array and if not its not proper set and answer won’t exist.
such as if we take S : ( a , b , c , a^b , b^c , c^a , d ) [extra element d present]
and if we use our previous X hence there answer is not possible not because we choose a wrong X value but because the set doesn’t have any possible X.
For this set to be proper it would be like this :
S : ( a , b , c , d , a^b , b^c , c^a , c^d , a^d , b^d , a^b^c , a^b^d, a^c^d )

Its just looks a little complicated but actually its really easy.

1 Like