MYXOR CAN ANYONE EXPLAIN IT

QUESTION:
https://www.codechef.com/problems/ROCXOR
CODE:
https://www.codechef.com/viewsolution/41970271

I AM NOT GETTING THE LOGIC CAN ANYONE EXAPLAIN IT

If you didn’t get the logic, how did you code the solution?

5 Likes

Hint:

since if, a ^ b = c then c ^ a = b and also c ^ b = a

1 Like

My Code is given TLE Please help Me

#include<bits/stdc++.h>
#define lli long long int
#define fast ios_base::sync_with_stdio(0);cin.tie(0);
#define vi vector
#define pb push_back
using namespace std;
int main()
{
lli t;
cin>>t;
while(t–)
{
lli n,x;
cin>>n>>x;
vi arr;
for(lli i=0;i<n;i++)
{
lli val;
cin>>val;
arr.pb(val);
}
sort(arr.begin(),arr.end());
lli v1=0,v2=0;
for(lli i=0;i<n;i++)
{
if(find(arr.begin(),arr.end(),arr[i]^x)!=arr.end()){
v1=arr[i];
v2=arr[i]^x;
break;
}
}
if(v1==0 && v2==0)
cout<<-1<<endl;
else
cout<<v1<<" "<<v2<<endl;
}
}

Instead of find function use map <int,bool> m ;
and store all elements in it at the time of input

sort vector
start from begin
int r = x^arr[i];
if ( m[r] == 1 ) print ( a[i] , r ) , break ;

find is taking O(n) while map will take O(1) for searching

Here is my solution
https://www.codechef.com/viewsolution/41957816

Instead of ‘find’ function use binary_search (arr.begin(),arr.end()), find takes O(n) in worst case so your solution is effectively O(n*n). :slightly_smiling_face:

1 Like

Thanks

Great question I seen editorial of someone else anyway I am going learn the core behind the code so what matter wheather I copy paste the code and it was not a live contest simple :slight_smile:

1 Like