Problem:

Given an array [math]V[/math] consisting of [math]N[/math] integers [math]V_1, V_2, \ldots V_n[/math]. Find [math]\bigoplus\limits_{1 \le i \le j \le N} (V_i + V_j)[/math]

Many a time, in xor-based problems, it helps to find the solution bit-by bit. And that will help here as well.

Let us try to answer the question: What is the [math]b[/math]th bit (from right) of the answer?

Consider all pairs of sums [math]V_i+V_j[/math]. Count how many of them have [math]b[/math]th bit as 1. If this number is odd, the [math]b[/math]th bit of the answer will be 1 and 0 otherwise.

So how can we calculate the number of pairs [math](i,j)[/math] such that the sum [math]V_i+V_j[/math] has [math]b[/math]th bit as one? Looping over all pairs is not going to work for the constraints.

Note that the [math]b[/math]th bit of the sum will only depend on the last [math]b[/math] bits of each number. Suppose that we have sorted all numbers based on the last [math]b[/math] bits. For a number [math]V_i[/math] in this array, which [math]V_j[/math]s such that [math]j>i[/math] give [math]b[/math] th bit as 1?

Clearly, the sum of two b-bit suffixes will lie in the range [math][0,2^{b+1}-2][/math]. Of these, the ranges [math][2^{b-1},2^b-1][/math] and [math][2^b+2^{b-1},2^{b+1}-2][/math] are the ranges with the [math]b[/math]th bit as one. For a given [math]V_i[/math], It is thus enough to count how many [math]V_j[/math]s exist such that their sum falls in these ranges. As we have sorted the array by the [math]b[/math]-bit suffix, this can be done using a binary search in [math]O(\log N)[/math] time. Or we can find the answer for all values of [math]i[/math] using a sliding window (two-pointers method) in [math]O(N)[/math].

Repeating this process for all bits will thus give the answer. Since there are 29 bits to take care of and a sorting step needs to be performed for each bit, we have a complexity of [math]O(29 N \log N)[/math]. However, if we follow a radix sort-like approach and start from the least significant bit, each sorting step can be reduced to [math]O(N)[/math] giving us a final complexity of [math]O(29 N)[/math].