COUPLING - Editorial

DIFFICULTY :
Cakewalk

PREREQUISITES :
Basic Math

PROBLEM :
Given an array of N integers we have to XOR each element with a certain number such that the resultant XOR is prime and the sum of the resultant XORs is minimum possible.

EXPLANATION :
It is easy to observe that XORing each number with 2(since it is the smallest prime number) which will give us the desired number.
The only exception here being 2 (since XORing it with 2 will result in 0 which is not allowed) thus we XOR all elements with A[i] = 2 with 3.

TIME COMPLEXITY :
The Time complexity is O(N).

Solution :

Solution

#include “bits/stdc++.h”
using namespace std;
void solve()
{
int n;
cin>>n;
vector a(n);
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n;i++)
{
if(a[i]==2)
cout<<(a[i]^3)<<" “;
else
cout<<(a[i]^2)<<” ";
}
cout<<endl;
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int tests;
//cin>>tests;
tests=1;
for(int i=0;i<tests;i++)
{
solve();
}
}