Distinct XOR Prefix Sums
MediumPractice library · +20 XPbit manipulationprefix sumshash set
Given an array A of N integers, find the number of distinct values of prefix XOR sums. The prefix XOR sum at index i is defined as A[0] ^ A[1] ^ ... ^ A[i].
Input
The first line contains an integer N. The second line contains N space-separated integers A[0], A[1], ..., A[N-1].
Output
Print a single integer: the count of distinct prefix XOR sums.
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
4 1 2 3 4
Output
4
Prefix XOR sums are: 1, 1^2=3, 1^2^3=0, 1^2^3^4=4. Distinct sums: {0, 1, 3, 4}. Count is 4.
Example 2
Input
5 5 5 5 5 5
Output
2
Prefix XOR sums are: 5, 5^5=0, 5^5^5=5, 5^5^5^5=0, 5^5^5^5^5=5. Distinct sums: {0, 5}. Count is 2.
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
4 1 2 3 4
Example 2 input
5 5 5 5 5 5