# Finding maximum and minimum of consecutive XOR values

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?

• Have you considered sorting your 'sum' list? It seems like adjacent values would be more likely to cancel a lot of bits and end up near 0. Dec 28, 2012 at 4:43

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.

• " Basically, the problem is, given n, k-bit integers Si, find i,j such that Si⊕Sj is maximum. " i don't understand this line. i want that Si⊕Si+1⊕ ...⊕ Sj to be maximum? correct me if i'm missing anything Dec 29, 2012 at 8:09
• @Aryabhata, it's unfair to consider $O(nk)$ linear. After all, $k \geq \log_2 n$, (unless the list can have duplicates). It's still a nice solution though. Dec 29, 2012 at 9:02
• @Aryabhata, because of that bound you might as well say the algorithm is $O(1)$. That's not very descriptive though. Dec 29, 2012 at 20:59
• The question does not say that the integers are bounded; it says that the array has size at most 50000. So in fact $n$ is constant, not $k$!! Jan 1, 2013 at 18:48
• @JeffE: Oh! And now that you point out (and I agree with that interpretation), Karolis' comments all make sense to me now. Thanks! Jan 2, 2013 at 6:04

Sorting helps with $\max$ too. A little bit, at least. Clearly, maximum would be reached by $x \oplus \neg x$. So for each $x = \text{sum}_i$ do a binary search for $\neg x$. That's $O(n \log n)$ time, same as sorting, so that remains to be the complexity of the whole procedure.

• what about min value? Dec 29, 2012 at 2:22
• what if i don't find ¬x ? Dec 29, 2012 at 2:25
• @palatok, min value was already explained. If you don't find $\neg x$, check the two sums closest to where it would be. Dec 29, 2012 at 8:54
• $sum_i, sum_j$ should be 0 or 1. Hash table will suffice. Dec 29, 2012 at 13:16
• @Strin, I don't see what you mean. $\text{sum}_i$ is $k$ bits long. How would a hash table be useful - close, not exact values are needed. Dec 29, 2012 at 14:15

Here is why Strilanc's suggestion works for $\min$. Consider your array $\mathrm{sum}$, and suppose the minimum is achieved by $a_p,a_q$, where $p<q$. Either $a_p = a_q$ (in which case $a_p = a_{p+1}$), or $a_p = x0y$, $a_q = x1z$ for some $x,y,z$. Suppose $q > p+1$, and let $a_{p+1} = xbw$. If $b = 0$ then $a_p \oplus a_{p+1} < a_p \oplus a_q$, while if $b = 1$ then $a_{p+1} \oplus a_q < a_p \oplus a_q$. Therefore $q = p+1$.