Count XOR Pairs
MediumPractice library · +20 XPbit manipulationhash mapprefix sums
Given an array of N integers, find the number of pairs (i, j) such that i < j and the bitwise XOR of the elements at these indices is equal to K. That is, count pairs (i, j) where 0 <= i < j < N and A[i] XOR A[j] == K.
Input
The first line contains two integers N and K, separated by a space. The second line contains N space-separated integers A_1, A_2, ..., A_N.
Output
Print a single integer, the total count of pairs (i, j) satisfying the conditions.
Constraints
1 <= N <= 200000 0 <= K < 2^30 0 <= A_i < 2^30
Time limit 1 s (native code; slower languages get more)Memory 256 MB14 hidden tests
Example 1
Input
5 7 1 5 3 4 2
Output
2
Pairs (3,4) and (5,2) have XOR sum 7. Indices (2,3) and (1,4). Count = 2.
Example 2
Input
3 0 1 1 1
Output
3
Pairs (1,1) at indices (0,1), (0,2), (1,2) have XOR sum 0. Count = 3.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 7 1 5 3 4 2
Example 2 input
3 0 1 1 1