Hints: XOR to All
First, apply the operation with the element at index
i. Then, apply the operation again with the element at index j. What does the final array look like?
After the first operation, the array is
a[1] ^ a[i], a[2] ^ a[i], a[3] ^ a[i] ....
After the second operation, the element at index j is a[i] ^ a[j]. If you apply the operation again, the array looks like:
(a[1] ^ a[i]) ^ (a[i] ^ a[j]), (a[2] ^ a[i]) ^ (a[i] ^ a[j]) , (a[3] ^ a[i]) ^ (a[i] ^ a[j]) ....
Since a[i] ^ a[i] = 0
a[1] ^ a[j], a[2] ^ a[j], a[3] ^ a[j] ....
Therefore, applying the operation multiple times is equivalent to applying the original element at the last index.
Try each index as the possible candidate.
Given an array, come up with an algorithm to answer multiple queries of the kind
a[1] ^ x + a[2] ^ x + a[3] ^ x + ....
Solve for each bit position independently. Precompute the number of set bits at all position. For a particular bit position, if there are
sbit[j] set bits and the corresponding bit in x is not set, the answer will increase by (sbit[j])*(2^j). If the corresponding bit in x is set, the answer will increase by (n - sbit[j])*(2^j).