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[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
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
First learn Trie data structure , then i will provide the source code