XOR Pairs with Zero Sum
MediumPractice library · +20 XPbit manipulationhash mapprefix sums
Given N integers A_1, A_2, ..., A_N, find the number of pairs (i, j) such that 1 <= i < j <= N and A_i ^ A_j = 0. The XOR operation (^) is the bitwise exclusive OR.
Input
The first line contains a single integer N. The second line contains N space-separated integers A_1, A_2, ..., A_N.
Output
Print a single integer: the number of pairs (i, j) with i < j and A_i ^ A_j = 0.
Constraints
1 <= N <= 200000 0 <= A_i <= 10^9
Time limit 1 s (native code; slower languages get more)Memory 256 MB14 hidden tests
Example 1
Input
5 1 2 3 2 1
Output
2
Pairs are (1, 4) for value 2 and (0, 3) for value 1. Indices are 0-based.
Example 2
Input
4 5 5 5 5
Output
6
All four 5s can form pairs. 4 choose 2 = 6 pairs.
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 1 2 3 2 1
Example 2 input
4 5 5 5 5