# XORR-Editorial

Setter: Utkarsh Gupta
Tester: Satyam, Utkarsh Gupta
Editorialist: Devendra Singh

To be calculated

# PROBLEM:

Chef has two arrays A and B, each of length N.

A pair (i,j) (1 \leq i \lt j \leq N) is said to be a good pair if and only if
A_i \oplus A_j = B_i \oplus B_j

Here, \oplus denotes the bitwise XOR operation.

Determine the number of good pairs.

# EXPLANATION:

Let us simplify the equation given in the problem by taking XOR with A_j\oplus B_i on both sides.
A_i \oplus A_j \oplus A_j \oplus B_i = B_i \oplus B_j \oplus A_j \oplus B_i
A_i \oplus B_i = A_j \oplus B_j
\therefore We need to find the number of pair (i,j) (1 \leq i \lt j \leq N) such that A_i \oplus B_i = A_j \oplus B_j
Iterate on the arrays from i=1 to N, keeping track of A_i\oplus B_i with the help of a map data structure. For each index i add the count of A_i\oplus B_i to the answer then update the count of A_i\oplus B_i in the map.

# TIME COMPLEXITY:

O(Nlog(N)) or for each test case.

# SOLUTION:

Setter's solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}

if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}

return x;
} else {
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}
int maxAi=((1<<30)-1);
int sumN=0;
int A[N],B[N],C[N];
void solve()
{
sumN+=n;
assert(sumN<=300000);
for(int i=1;i<=n;i++)
{
if(i==n)
else
}
for(int i=1;i<=n;i++)
{
if(i==n)
else
}
set <int> s;
map <int,ll> cnt;
for(int i=1;i<=n;i++)
{
C[i]=(A[i]^B[i]);
s.insert(C[i]);
cnt[C[i]]++;
}
ll ans=0;
for(auto it:s)
ans+=((cnt[it]*(cnt[it]-1))/2);
cout<<ans<<'\n';
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
while(T--)
solve();
assert(getchar()==-1);
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
void sol(void)
{
ll n, ans = 0;
cin >> n;
map<ll, ll> cnt;
vll a(n), b(n);
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
for (int i = 0; i < n; i++)
{
cin >> b[i];
ans += cnt[a[i] ^ b[i]];
cnt[b[i] ^ a[i]]++;
}
cout << ans << '\n';
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}

3 Likes
#include <bits/stdc++.h>
#define ull unsigned long long int
#define ui unsigned int
#define ll long long int
#define f(i, n) for (ll i = 0; i < n; i++)
const ll m = 10e9 + 7;
// const ll N = 10e5 + 5;
using namespace std;

ll binpow(ll a, ll b, ll m)
{
a %= m;
ll res = 1;
while (b > 0)
{
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ll t;
cin >> t;
while (t--)
{
ll n;
cin >> n;
ll arr1[n];
ll arr2[n];
f(i, n) cin >> arr1[i];
f(i, n) cin >> arr2[i];
unordered_map<ll, ll> map;
for (int i = 0; i < n; i++)
map[arr1[i] ^ arr2[i]]++;
int ans = 0;
for(auto& i : map){
ans += ((i.second*(i.second-1))/2);
}
cout << ans << '\n';
}
return 0;
}
please anyone tell why this is giving WA in one testcase.


Change int ans to long long ans as N is large and answer could be very large ((N*(N-1))//2) exceeding the range of int

2 Likes

We have to check Ai ^ Bi == Aj ^ Bj then why we are considering only Ai ^ Bi

// whats wrong in my code ?

using namespace std;

int main()

{

int t;

cin >> t;

while (t--)

{

int counter = 0;

int n;

cin >> n;

int a[n], b[n];

for (int i = 0; i < n; i++)

cin >> a[i];

for (int i = 0; i < n; i++)

cin >> b[i];

for (int i = 0; i < n - 1; i++)

{

for (int j = i + 1; j < n; j++)

{

if ((a[i] ^ a[j + 1]) == (b[i] ^ b[j + 1]))

{

counter++;

}

}

}

cout << counter << "\n";

}


}

the time complexity is O(nĖ2) which would end up in TLE.
Also if you are looping j from i+1 to n, then indexing j+1 will result in a segmentation fault as well.

I was using the standard bruteforce approach lol.