You are given an array A. You have to choose an element from this array say A[k] and form a new array B such that B[i] = A[i]^A[k]. (^ means bitwise XOR).
Now the score of the array would be the sum of all elements of B.
The task is to find the element with which the score of the array would be maximum.
Example-
If A = [15,11,8]
and we choose A[k] = 15 then B would be [0,4,7] (15^15=0,15^11=4,15^8=7). The score would be 0 4 7 = 11 which is the maximum we can get by choosing any element as A[k].
Another Example-
If A = [11,12,13,14,15] maximum possible score=22.
How can we solve this problem to choose an element which yields the maximum score.
How to solve this question or how to proceed with such questions?

CodePudding user response：

The answer to many xor algorithm problems is to work bit by bit. Here, if for each bit position you count the number of array elements that have that bit set (which incidentally tells you how many array elements don't have that bit set by subtracting from the array length), you have a way of quickly computing sum(A[i] xor X) for any X, by considering the part of the sum that's contributed by each possible bit. That way of computing the sum depends on the bit width of the largest number in the array, but not on the length of the array.

Once you've done that, you can simply go through the array and find the element that maximizes the sum.

If you do this right, then the algorithm is O(NW) where N is the length of the input array, and W is the smallest number such that each of the input numbers fit in a W-bit integer. And it'll use O(W) additional storage. (Typically, these algorithm problems limit the size of the inputs so they fit in an int32 or int64, so W will be 32 or 64).