Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
1  
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. –  Strilanc Dec 28 '12 at 4:43

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
    
" 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 –  palatok Dec 29 '12 at 8:09
1  
@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. –  Karolis Juodelė Dec 29 '12 at 9:02
1  
@Aryabhata, because of that bound you might as well say the algorithm is $O(1)$. That's not very descriptive though. –  Karolis Juodelė Dec 29 '12 at 20:59
1  
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$!! –  JeffE Jan 1 '13 at 18:48
1  
@JeffE: Oh! And now that you point out (and I agree with that interpretation), Karolis' comments all make sense to me now. Thanks! –  Aryabhata Jan 2 '13 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.

share|improve this answer
    
what about min value? –  palatok Dec 29 '12 at 2:22
    
what if i don't find ¬x ? –  palatok Dec 29 '12 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. –  Karolis Juodelė Dec 29 '12 at 8:54
    
$sum_i, sum_j$ should be 0 or 1. Hash table will suffice. –  Strin Dec 29 '12 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. –  Karolis Juodelė Dec 29 '12 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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.