maximum XOR

Maximum XOR value of a pair from a range

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

#include <bits/stdc++.h> using namespace std; #define INF 1<<30 #define MAX 10005 #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); typedef long long ll; int MaxXORInRange(int l, int r) { int LXR = l ^ r; // xor limits int msbPos = 0; while(LXR){ msbPos++; LXR >>= 1; } int maxXOR = 0; int two = 1; while(msbPos--){ maxXOR += two; two <<= 1; } return maxXOR; } int main() { FASTIO ///* //double start_time = clock(); #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); freopen("error.txt", "w", stderr); #endif //*/ int L,R; cin >> R >> R; cout << MaxXORInRange(L,R)<<endl; //double end_time = clock(); //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); return 0; }

Find the maximum subarray XOR in a given array

 O(N^2) solution

Anther O(N) solution using Trie Tree:  Gist_Link

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

#include <bits/stdc++.h> using namespace std; #define INF 1<<30 #define MAX 10005 #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); typedef long long ll; #define INT_SIZE 32 struct TrieNode { int value; TrieNode *ar[2]; }; TrieNode *newNode() { TrieNode *temp = new TrieNode; temp->value = 0; temp->ar[0] = temp->ar[1] = NULL; return temp; } void insert(TrieNode *root, int pre_xor) { TrieNode *temp = root; for(int i = INT_SIZE - 1; i >= 0; i--){ bool val = pre_xor & (1 << i); if(temp->ar[val] == NULL) temp->ar[val] = newNode(); temp = temp->ar[val]; } temp->value = pre_xor; } int query(TrieNode *root, int pre_xor) { TrieNode *temp = root; for(int i = INT_SIZE - 1; i >= 0; i--){ bool val = pre_xor & (1 << i); if(temp->ar[1-val] != NULL) temp = temp->ar[1-val]; else if(temp->ar[val] != NULL) temp = temp->ar[val]; } return pre_xor ^ (temp->value); } int maxSubarrayXOR(int ar[], int n) { TrieNode *root = newNode(); insert(root, 0); int res = INT_MIN, pre_xor = 0; for(int i = 0; i < n; i++){ pre_xor = pre_xor ^ ar[i]; insert(root, pre_xor); res = max(res, query(root, pre_xor)); } return res; } int main() { FASTIO ///* //double start_time = clock(); #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); freopen("error.txt", "w", stderr); #endif //*/ int n; cin >> n; int a[n+2]; for(int i = 0; i < n; i++){ cin >> a[i]; } cout << maxSubarrayXOR(a,n)<< endl; //double end_time = clock(); //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); return 0; }

Share: