Count Pairs with Equal XOR Sum
Given an array of N integers, find the number of pairs (i, j) such that i < j and the bitwise XOR sum of the subarray from index i to j (inclusive) is 0. The bitwise XOR sum of a subarray a[i...j] is defined as a[i] ^ a[i+1] ^ ... ^ a[j].
Input
The first line contains an integer N. The second line contains N space-separated integers a_1, a_2, ..., a_N.
Output
Print a single integer, the count of pairs (i, j) with i < j and XOR sum of a[i...j] equal to 0.
Constraints
1 <= N <= 200000 0 <= a_i <= 10^9
Example 1
4 1 2 3 0
3
Pairs are (1,2) with XOR sum 3^0=3, (1,3) with 2^3^0=1, (2,3) with 3^0=3. Pairs with XOR sum 0: (0,3) a[0]^a[1]^a[2]^a[3] = 1^2^3^0 = 0. (3,3) a[3]=0. Count = 2.
Example 2
5 4 2 2 6 4
2
Pairs with XOR sum 0: (1,2) a[1]^a[2] = 2^2=0. (0,5) a[0]^...^a[4] = 4^2^2^6^4=0. (3,4) a[3]^a[4] = 6^4=2. (0,3) a[0]^...^a[3] = 4^2^2^6=0. Count = 3.
Hints
Similar problems
- Subsegment Sum Divisible by KMedium
- Subarray Sum MultiplesMedium
- Subarray Sums with Target DifferenceMedium
- Distinct Elements in PrefixMedium
- Matrix Zero Sum SubgridsMedium
- Count Subarrays with Target Sum DifferenceMedium
More topics: Hash Map and Hashing problems, Prefix Sums problems, Recursion problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
4 1 2 3 0
5 4 2 2 6 4