[Coding] Chef Find XOR Beautiful solution codechef

Chef Find XOR Beautiful solution codechef

 

You are given an array AA of size NN and an integer XX.

Find the count of all the pairs (i,j)(i,j) such that ((AiAj)((Ai⊕Aj) && X)=0X)=0. Here  and && denote bitwise XOR and bitwise AND operations respectively.

Input Format

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains a single integer NN – the size of the array.
  • The second line contains NN space-separated integers A1,A2,,ANA1,A2,…,AN – the elements of the array.
  • The third line of each test case contains a single integer XX.

Output Format

Chef Find XOR Beautiful solution codechef

For each test case, print a single line containing one integer ― the total number of pairs satisfying the condition.

Constraints

  • 1T101≤T≤10
  • 1N1051≤N≤105
  • 0Ai,X1090≤Ai,X≤109

Sample Input 1 

2
4
1 2 3 1
1
3
0 0 0
21

Sample Output 1

Chef Find XOR Beautiful solution codechef

10
9

Explanation

Test case 11: There are 1010 pairs of (i,j)(i,j) (1i,jN)(1≤i,j≤N) satisfying the condition. These pairs are: (1,1),(1,3),(1,4),(2,2),(3,1),(3,3),(3,4),(4,1),(4,3),(1,1),(1,3),(1,4),(2,2),(3,1),(3,3),(3,4),(4,1),(4,3), and (4,4)(4,4).

Test case 22: There are 99 pairs of (i,j)(i,j) (1i,jN)(1≤i,j≤N) satisfying the condition. These pairs are: (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2), and (3,3)(3,3).

ANSWER

Click Here

Leave a Comment