I can't understand this question

,
1

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

A pair (i,j) (1≤i<j≤N) is said to be a good pair if and only if

Ai⊕Aj=Bi⊕Bj

Here, ⊕ denotes the bitwise XOR operation.

Determine the number of good pairs.

Input Format

  • The first line of input will contain a single integer T, denoting the number of test cases. The description of the test cases follows.
  • Each test case consists of three lines of input:
    • The first line contains a single integer N — the size of the arrays A and B.
    • The second line contains N space-separated integers A1,A2,…,AN — the elements of array A.
    • The third line contains N space-separated integers B1,B2,…,BN — the elements of array B.

Output Format

  • For each test case, output on a new line the number of good pairs.

Constraints

  • 1≤T≤105
  • 2≤N≤3⋅105
  • The sum of N over all test cases does not exceed 3⋅105
  • 0≤Ai,Bi<230

Sample Input 1

2
4
1 2 3 4
4 3 2 1
5
1 3 4 7 9
5 1 0 5 13

Sample Output 1

2
4

Explanation

Test Case 1: There are 2 good pairs: (1,4) and (2,3). This is because A1⊕A4=1⊕4=B1⊕B4, and A2⊕A3=2⊕3=B2⊕B3.

Test Case 2: The 4 good pairs are (1,3), (2,4), (1,5) and (3,5). For example, (2,4) is good because A2⊕A4=3⊕7=4 and B2⊕B4=1⊕5=4.

2

The equation can be rewritten as as A_{i} \oplus B_{i} = A_{j} \oplus B_{j}. The answer to the problem can be expressed as \sum\limits_{k = 1}^{n} \binom{V_k}{2}, where V_k is the number of indices in the array where the distinct value A_i \oplus B_i appears, and n is the number of such distinct values.

3

  • See if you use brute force then Complexity will be O(n^2) which will give TLE.

  • So we will try to change the equation Ai⊕Aj=Bi⊕Bj in such a way that we can solve this question in O(n) time.

  • Steps for doing modifications to the above equation:

    Step 1) Do XOR on both sides by Aj.

    • Ai⊕Aj⊕Aj=Bi⊕Bj⊕Aj ( we know, x⊕x=0)
    • Ai⊕0 = Bi⊕Bj⊕Aj (we know, x ⊕ 0 = x ) { since if x=1, then 1⊕0=1 and if x=0, 0⊕0=0 }
    • Ai=Bi⊕Bj⊕Aj

    Step 2) Do XOR on both sides by Bi.

    • Ai⊕Bi=Bi⊕Bj⊕Aj⊕Bi
    • Ai⊕Bi=Bi⊕Bi⊕Bj⊕Aj (since xor is commutative)
    • Ai⊕Bi=0⊕Bj⊕Aj (we know, x⊕x=0)
    • Ai⊕Bi=Bj⊕Aj (we know, x ⊕ 0 = x )

Now the problem becomes simple. We will just find the pairs of Ai⊕Bi and store their frequency.
And our answer will then be their freq*(freq-1)/2.
Since if we have N pairs, then no. of distinct pairs will be nC2 or n*(n-1)/2.