# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Vibhu Garg

Tester: Manan Grover, Abhinav sharma

Editorialist: Devendra Singh

# DIFFICULTY:

2256

# PREREQUISITES:

# 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

- (A_i | A_j) denotes Bitwise OR operation,
- (A_i \oplus A_j) denotes Bitwise XOR operation,
- (A_i \& A_j) denotes Bitwise AND operation.

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); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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();
}
```