 # ABITEZ-Editorial

Setter: Vibhu Garg
Tester: Manan Grover, Abhinav sharma
Editorialist: Devendra Singh

2256

# PROBLEM:

Chef was impressed by an array A of N non-negative integers. But, he was asked to solve the following problem in order to get this array.

Given a non-negative integer k, find the number of pairs (i, j) (1 \leq i < j \leq N) such that the following condition holds true:
(A_i | A_j) + (A_i \oplus A_j) + (A_i \& A_j) = k + A_j, where

You, being Chef’s friend, help him get this array by solving the above problem.

# EXPLANATION:

Observation

(a|b) = (a \oplus b) + (a & b).
(a + b) = (a \oplus b) + 2\cdot (a & b)
\therefore (a| b) + (a \oplus b) + (a & b) = (a \oplus b) + (a \oplus b) + (a & b) + (a & b) = (a \oplus b) + (a + b).

The equation in the question is same as (A_i \oplus A_j) + (A_i + A_j)=(K + A_j).
\implies(A_i \oplus A_j) = (K-A_i).
\implies A_j = ((K-A_i) \oplus A_i).
Thus for each index i we need to find indices j such that i<j and A_j = ((K-A_i) \oplus A_i). This can easily be done using a map.

# TIME COMPLEXITY:

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

# SOLUTION:

Setter's solution
#include <bits/stdc++.h>
#define ll long long int
using namespace std;

int main(){

int t;
cin >> t;

while(t--){

ll n, k;
cin >> n >> k;

vector <ll> v(n);
map <ll, ll> freq;

for(ll i = 0; i < n; i++){
cin >> v[i];
}

ll ans = 0;

for(ll i = n - 1; i >= 0; i--){
ll req = (k - v[i]) ^ (v[i]);
ans += freq[req];
freq[v[i]]++;
}

cout << ans << endl;
}
}

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>
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, k, ans = 0;
cin >> n >> k;
vll v(n);
for (int i = 0; i < n; i++)
cin >> v[i];
map<ll, ll> cnt;
for (int i = n - 1; i >= 0; i--)
{
if (k >= v[i])
ans += cnt[v[i] ^ (k - v[i])];
cnt[v[i]]++;
}
cout << ans << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}


12 Likes

how the equation is same as (Ai^Aj)+(Ai+Aj)=K+Aj
i didn’t get it

1 Like

(Ai | Aj ) + (Ai & Aj ) = Ai + Aj

OR captures bits present in both Ai and Aj
AND captures bits when present in both Ai and Aj
so combined captures all the bits of Ai and Aj

example
Ai => 6 = 110
Aj => 5 = 101
bitCount= 211

Ai|Aj = 111
Ai&Aj = 100
bitCount= 211


hence sum would be same

5 Likes
   (Ai xor Aj) + (Ai or Aj) + (Ai and Aj) = k + Aj
⟹ (Ai xor Aj) + ( (Ai xor Aj) + (Ai and Aj) ) + (Ai and Aj) = k + Aj [As,or = xor + and ]
⟹ (Ai xor Aj) + (Ai xor Aj) + 2*(Ai and Aj) = k + Aj
⟹ (Ai xor Aj) + (Ai + Aj) = k + Aj [As,sum = xor + 2*and ]

3 Likes

Nice problem!

A&B = SET BITS that are BOTH in A&B
A-(A&B) = SET BITS that are ONLY in A
A-(A&B) + B = SET BITS that are either in A or B – >( A|B)
therefore :
A - (A&B) + B = (A|B)
A+B = (A&B)+(A|B)

1 Like

Wouldn’t having a map/hash table for all the indices of the array create a huge auxillary space issue?

Given: (Ai | Aj) + (Ai ^ Aj) + (Ai & Aj) = k +Aj
Try this: 2 * (Ai | Aj) == k + Aj
because:
& OR^ == Bitwise OR (|)
i j & ^ |
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 0 1