Good Pairs codechef solution

 

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

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

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.

Output Format

Good Pairs codechef solution

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

Constraints

• 1≤T≤1051≤T≤105
• 2≤N≤3⋅1052≤N≤3⋅105
• The sum of NN over all test cases does not exceed 3⋅1053⋅105
• 0≤Ai,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

Sample Output 1 

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 A1⊕A4=1⊕4=B1⊕B4A1⊕A4=1⊕4=B1⊕B4, and A2⊕A3=2⊕3=B2⊕B3A2⊕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 A2⊕A4=3⊕7=4A2⊕A4=3⊕7=4 and B2⊕B4=1⊕5=4B2⊕B4=1⊕5=4.

 

SOLUTION

“Click here“