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 $(pleq q)$ is: $X = text{sum}_q oplus text{sum}_{p-1}$. Thus: $$ mathrm{MinAns} = min_{(p,q) text{ s.t. } ple q}{text{sum}_q oplus text{sum}_{p-1}} mathrm{MaxAns} = max_{(p,q) text{ s.t. } ple 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
