sum of xor values of all pairs
algorithm, xor
Solution
You can separate the calculation to do one bit at a time.
For example, look at the rightmost bit of all the numbers in the array. Suppose that `a` numbers have a rightmost 0-bit, and `b` numbers have a 1-bit. Then out of the pairs, `a*b` of them will have 1 in the rightmost bit of the XOR. This is because there are `a*b` ways to choose one number that has a 0-bit and one that has a 1-bit. These bits will therefore contribute `a*b` towards the total of all the XORs.
In general, when looking at the `n`th bit (where the rightmost bit is the 0th), count how many numbers have 0 (call this an) and how many have 1 (call this bn). The contribution towards the final sum will be an*bn*2n. You need to do this for each bit and sum all these contributions together.
This can be done in O(kn) time, where `k` is the number of bits in the given values.
Problem
We have an array `A (say [1,2,3])` . We need to find the XOR(^)SUM of all pairs of integers in the array. Though this can easily be done in `O(n^2)` but how can i improve the complexity of the solution ? E.g for the above array , A, the answer would be `(1^2)+(1^3)+(2^3) = 6` Thanks.