Finding maximum and minimum of consecutive XOR values

Problem Detail: 

Given an integer array (maximum size 50000), I have to find the minimum and maximum $X$ such that $X = a_p \oplus a_{p+1} \oplus \dots \oplus a_q$ for some $p$, $q$ with $p \leq q$.

I have tried this process: $\text{sum}_i = a_0 \oplus a_1 \oplus \dots \oplus a_i$ for all $i$. I pre-calculated it in $O(n)$ and then the value of $X$ for some $p$, $q$ such that $(p\leq q)$ is: $X = \text{sum}_q \oplus \text{sum}_{p-1}$. Thus:

$$ \mathrm{MinAns} = \min_{(p,q) \text{ s.t. } p\le q}{\text{sum}_q \oplus \text{sum}_{p-1}} \\ \mathrm{MaxAns} = \max_{(p,q) \text{ s.t. } p\le q}{\text{sum}_q \oplus \text{sum}_{p-1}} \\ $$

But this process is of $O(n^2)$. How can I do that more efficiently?

Asked By : palatok

Answered By : Aryabhata

If $k$ is the bitsize of the integers, then you can compute the Max in $O(n k)$ time.

Basically, the problem is, given $n$, $k$-bit integers $S_i$, find $i,j$ such that $S_i \oplus S_j$ is maximum.

You treat each $S_i$ as a binary string (looking at the binary representation), and create a trie out of those strings. This takes $O(nk)$ time.

Now for each $S_j$, you trying walking the complement of $S_j$ in the trie you created (taking the best branch at each step basically), finding a $j'$ such that $S_j \oplus S_{j'}$ is maximum.

Do this for each $j$, and you find the answer in $O(n k)$ time.

Since your integers are bounded, this algorithm for max is basically linear, and so is the algorithm for min got by sorting (as sorting can be done in linear time).

Incidentally, if there were no bounds, then you can reduce element distinctness to the min version.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7622