 # How to find maximum xor prefix and suffix optimally?

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

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 , Array … 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

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

@vipsharmavip
Can you provide the source code.

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

@vipsharmavip

I have learnt it.