Posted in: trivia

Good Pairs codechef solution

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


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.


  • 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 

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

Sample Output 1 

Good Pairs codechef solution



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.



Click here

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to Top