QUESTION:

https://www.codechef.com/problems/ROCXOR

CODE:

https://www.codechef.com/viewsolution/41970271

I AM NOT GETTING THE LOGIC CAN ANYONE EXAPLAIN 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).

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

1 Like