4

I have following problem : given an integer array (maximum size 50000) i have to find the maximum X such that,

X = a[p] ^ a[p+1] ^ ... ... ^ a[q] for some p,q (p<=q)

Also i have to find the minimum value of X.

I have tried this process ,

sum[i] = a[0] ^ a[1] ^ ... ... ^ a[i] for some i .

i pre-calculated it in O(n) and

then the value of X for some p,q(p<=q) is ,

X = sum[q] ^ sum[p-1]

MaxAns = Max of X for every pair of p,q (p<=q)

MinAns = Min of X for every pair of p,q (p<=q)

But this process is O(n^2).

How can i do that without O(n^2) algorithm , something more efficient ?

2
  • Not that it really helps you but if I remember properly, there's a problem which looks like this one in "Programming Pearls". I think this is it with addition instead of XOR (I don't know how much of it you can adapt), in Column 8 "Algorithm design techniques".
    – SylvainD
    Dec 28 '12 at 3:37
  • i'm sorry, what is "Programming perls"?
    – palatok
    Dec 28 '12 at 3:42
4

This algorithm works only for unsigned integers with limited bit width.

  1. Calculate prefix sum for each array element (exactly as this is done in OP).
  2. Add each prefix sum to a radix tree (most significant bit corresponding to the root, least significant bit corresponding to leafs).
  3. Between calculating sum[q] and adding it to the radix tree, search sum[q] in the partially built radix tree (to get a minimum value of X). For maximum value of X, search ~sum[q].
  4. If any bit of sum[q] (or ~sum[q]) is missing from the tree, toggle this bit in the min/max value of X and continue search down the tree.
  5. Get minimum/maximum of all min/max values, found for each prefix.

Time complexity is O(N log M), where M is the maximum value of array's elements.

2
  • thanks a lot for your thoughtful answer. i don't know the radix tree data structure (my bad !) , can you give me some link from where i can learn the implementation of radix tree FOR SOLVING MY PROBLEM. thanks again.
    – palatok
    Dec 28 '12 at 16:34
  • @palatok: I think Wikipedia article contains pretty good explanation: Radix tree. Or you can use a simpler (but less efficient) structure instead: Trie. Dec 28 '12 at 16:54
1

This is plain wrong - not sure why but a bit of testing seems to show it's wrong.

I think you can get some inspiration from the column 8 of "Programming Pearls" where the problem is basically : "Given the real vector x[n], compute the maximum sum found in any contiguous subvector".

I think you can reuse the different algorithms replacing additions and subtractions by exclusive-or (most of the interesting properties are kept during the process : 0 is still the neutral elements, exclusive-or is its own inverse, commutativity).

You can find the slides : http://cs.bell-labs.com/cm/cs/pearls/s08.pdf but I definitely recommend the book.

2
  • If this is the algorithm I think it is, it won't work even in simple cases like [1,3].
    – Nabb
    Dec 28 '12 at 5:22
  • Arg, I'll try this later out of curiosity. Sorry for this.
    – SylvainD
    Dec 29 '12 at 21:28
0

Algorithm :

Initialize:

ans=a[0]
cur=a[0]

Loop for each element of the array:

(a) cur = max(a[i], cur^a[i])
(b) ans = max(cur, ans)
return ans

Example : Let array be 1 2 3 5 8 10

ans=cur=1

for i=1:

cur = max(2,3) = 3

ans = max(1,3) = 3


for i=2:

cur = max(3,0) = 3

ans = max(3,3) = 3


for i=3:

cur = max(5,6) = 6

ans = max(6,3) = 6


for i=4:

cur = max(8,14) = 14

ans = max(6,14) = 14


for i=5:

cur = max(10,4) = 10

anx = max(14,10) = 14

So, ans = 14

Here is my implentation in C++

int maxXOR(int a[], int n)
{
    int ans = a[0],cur=a[0];
    for(int i=1;i<n;i++)
    {
        cur=std::max(a[i],cur^a[i]);
        ans=std::max(ans,cur);
    }
    return ans;
}

Analysis :

Time Complexity : O(n)
Space Complexity : O(1)
3
  • For this array : {6, 8, 2, 4, 2} your program gives 8 as output BUT right answer is 14. Sorry to say, you wrote the algorithm without completely understanding the problem.
    – palatok
    Jun 3 '14 at 10:29
  • It gives 14, I checked it again. But still if you wish, I can put my main() function also over here. Jun 5 '14 at 7:08
  • For the array {2,4,3} your code will give output as 6 but the correct answer is 7.
    – rohit
    Sep 8 '15 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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