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 ?

link

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

thanks for answer .

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

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