How to find maximum xor prefix and suffix optimally?

general
, , ,
1

What could be the most optimized solution to this problem and please also suggest some variations in this problems which I can prepare.

1 Like
2

This problem can be solved using Trie data structure with time complexity( N * Bits_size ) , where size of bit is depend on constraint , if elements are in the range of integer , then the time complexity should be O(N * 32 )

Step 1 : First insert Nth element in the tire , then insert xor ( A[ N ] , A[ N - 1 ] ) , then xor ( A[N] , A[N-1] , A[N-2] ) ans so on… till the 1st element.

And make an array suffix , where suffix[i] = xor( Array[i] , Array[i + 1] … Array[N]);

Now, to calculate answer , start from starting index , and remove the contribution of suffix[i] from the trie , and find the maximum xor we can obtained from the trie with prefix[i] , where prefix[i] = xor( Array[1] , Array[2] … Array[i] ) and from that we should be able to calculate the maximum xor value of suffix[i] with prefix[j] , where 1 <= i < j <= N with complexity ( N * Bit_size )

Here, I am assuming that the prefix and suffix we are considering are not overlap means for any prefix the starting index of suffix should be greater the ending index of prefix.

1 Like
3

@vipsharmavip
Can you provide the source code.

4

First learn Trie data structure , then i will provide the source code

5

@vipsharmavip

I have learnt it.

6

Implementation:
#define vipsharmavip

#include<bits/stdc++.h>

#define ll long long

using namespace std;

struct trie{

int ct;

struct trie *left , *right;

trie(): ct(0),left(NULL),right(NULL) {}

};

void Insert( trie *root , int level , int x , int change ){

if(level < 0 )

return;

if(  (x & (1 << level)) == 0 ){

    if(root->left == NULL )

     root->left = new trie();

     root->left->ct += change;

     Insert( root->left , level - 1 , x , change );

} else {

    if(root->right == NULL )

     root->right = new trie();

     root->right->ct += change;

     Insert( root->right , level - 1 , x , change );

}

}

ll query(trie * root , int level , int x ){

        if(root == NULL )

        return 0;

    if(level < 0 )

    return 0;

    if((1 << level) & x ){

      if(root->left != NULL ){

                  if(root->left->ct)

                  return (1 << level ) + query( root->left , level - 1 , x );
                  else

                            return query( root->right , level - 1 , x );


      } else

      return query( root->right , level - 1 , x );
    } else 
 {
      if(root->right != NULL ){

                  if(root->right->ct)

                  return (1 << level ) + query( root->right , level - 1 , x );

                  else

                            return query( root->left , level - 1 , x );


      } else

      return query( root->left , level - 1 , x );

    }

}

int main(){

trie *root = new trie();

           cin.sync_with_stdio(false);

               int N;
               cin >> N;

          int Array[N];

           for(int i = 0 ; i  < N ; ++i )  cin >> Array[i];

           int sufffix[N+1];
           int xr = 0;
           for(int i = N - 1 ; i >= 0 ; --i ){
           xr = (xr ^ Array[i]);
           sufffix[i] = xr;
           Insert(root , 30 , xr , 1 );
           }
            int Ans = 0;
            xr = 0;
            for(int i = 0 ; i < N - 1; ++i ){
                  Insert(root , 30, sufffix[i] , -1 );                       // remove the contribution of suffix starting from ith index
                  xr = (xr ^ Array[i]);
                  int value = query( root , 30 , xr );
                  Ans = max(Ans  , value );
            }

            cout << Ans << endl;

    return 0;

}

1 Like