How do we find no.of subarrays such that xor of its elements is equal to the sum of its elements?

p.s:the editorial used sliding window ,but i don’t understand the reason y it works

How do we find no.of subarrays such that xor of its elements is equal to the sum of its elements?

p.s:the editorial used sliding window ,but i don’t understand the reason y it works

Xor sum is normal sum, but without carryovers, which means, that if any bit is repeated, then xor sum is not equal to sum.

3 Likes

thnx ,but how do you come up with such an intuition ??

thats what xor do take example

`0010`

= 2

`0001`

= 1

now their xor = `0011`

= 3

sum = 1 + 2 = 3

if we add 3 (`0011`

) to array (repeating bits in their binary representation.)

xor = `0000`

= 0

sum = 1 + 2 + 3 = 6

so you can see how we come up to that intuition.

more formally you would want to know the length of subarray that starts from ith index, and can easily computer answer from there.

1 Like