A XOR operation

1

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

2

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 :slight_smile:

#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
3

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

4

check this post

1 Like
5

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