Posted in: trivia

# Good Pairs codechef solution

Chef has two arrays AA and BB, each of length NN.

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

AiAj=BiBjAi⊕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 TT, 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 NN — the size of the arrays AA and BB.
• The second line contains NN space-separated integers A1,A2,,ANA1,A2,…,AN — the elements of array AA.
• The third line contains NN space-separated integers B1,B2,,BNB1,B2,…,BN — the elements of array BB.

# Good Pairs codechef solution

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

### Constraints

• 1T1051≤T≤105
• 2N31052≤N≤3⋅105
• The sum of NN over all test cases does not exceed 31053⋅105
• 0Ai,Bi<2300≤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


# Good Pairs codechef solution

2
4


### Explanation

Test Case 11: There are 22 good pairs: (1,4)(1,4) and (2,3)(2,3). This is because A1A4=14=B1B4A1⊕A4=1⊕4=B1⊕B4, and A2A3=23=B2B3A2⊕A3=2⊕3=B2⊕B3.

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