Hey, I recently got this problem in an online assessment.
Count number of subarrays such that, xor of first and last element of subarray should be equal to xor of remaining elements in the subarray. And the minimum size of subarray in consideration would be greater than equal to 3.
Thanks
this means the subarray's xor=0
No, let's say subarray looks something like this: [a,b, c, d, e]. Xor of a and e should equal to b^c^d.
Yes, now that I think the way I descibed, it means exactly what you're saying.
Ig this problem came in one of CodeChef contest
Let's consider the prefix xor array $$$p[i]$$$, then the condition can be rewritten as $$$a[l] \oplus a[r] = p[l] \oplus p[r - 1]$$$. You can rewrite the condition again as $$$a[l] \oplus p[l] = a[r] \oplus p[r - 1]$$$ and then all you have to do is iterate from the suffix, maintain a counter $$$cnt$$$ for $$$a[r] \oplus p[r - 1]$$$ and add $$$cnt[a[i] \oplus p[i]]$$$ to the answer.
Here's an $$$O(N)$$$ solution:
We want to count subarrays such that:
$$$a[l] \oplus a[r] = a[l+1] \oplus \dots \oplus a[r-1]$$$
$$$0 = a[l] \oplus \dots \oplus a[r]$$$
$$$a[1] \oplus \dots \oplus a[l-1] = a[1] \oplus \dots a[r]$$$
Now, for a fixed $$$r$$$, we just need to count the number of $$$l$$$ such that the equation is true. We can do so in $$$O(1)$$$ via prefix sums stored in a hashmap.
Code:
Amazing man!
I guess you can just count the number of subarrays with 0 xor, by using prefix_xor and some combinatorics