Homework SourseNeed this in JAVA We have N numbers as an array you need to
Need this in JAVA
We have N numbers as an array, you need to find a prefix array and a suffix array, which we can get the maximum x or value with all elements in them. Notice that for prefix[0, 1] and suffix[r, n - 1], do not intersect (ISolution
// C++ program for a Trie based O(n) solution to find max
// subarray XOR
#include<bits/stdc++.h>
using namespace std;
// Assumed int size
#define INT_SIZE 32
// A Trie Node
struct TrieNode
{
int value; // Only used in leaf nodes
TrieNode *arr[2];
};
// Utility function tp create a Trie node
TrieNode *newNode()
{
TrieNode *temp = new TrieNode;
temp->value = 0;
temp->arr[0] = temp->arr[1] = NULL;
return temp;
}
// Inserts pre_xor to trie with given root
void insert(TrieNode *root, int pre_xor)
{
TrieNode *temp = root;
// Start from the msb, insert all bits of
// pre_xor into Trie
for (int i=INT_SIZE-1; i>=0; i--)
{
// Find current bit in given prefix
bool val = pre_xor & (1<<i);
// Create a new node if needed
if (temp->arr[val] == NULL)
temp->arr[val] = newNode();
temp = temp->arr[val];
}
// Store value at leaf node
temp->value = pre_xor;
}
// Finds the maximum XOR ending with last number in
// prefix XOR \'pre_xor\' and returns the XOR of this maximum
// with pre_xor which is maximum XOR ending with last element
// of pre_xor.
int query(TrieNode *root, int pre_xor)
{
TrieNode *temp = root;
for (int i=INT_SIZE-1; i>=0; i--)
{
// Find current bit in given prefix
bool val = pre_xor & (1<<i);
// Traverse Trie, first look for a
// prefix that has opposite bit
if (temp->arr[1-val]!=NULL)
temp = temp->arr[1-val];
// If there is no prefix with opposite
// bit, then look for same bit.
else if (temp->arr[val] != NULL)
temp = temp->arr[val];
}
return pre_xor^(temp->value);
}
// Returns maximum XOR value of a subarray in arr[0..n-1]
int maxSubarrayXOR(int arr[], int n)
{
// Create a Trie and insert 0 into it
TrieNode *root = newNode();
insert(root, 0);
// Initialize answer and xor of current prefix
int result = INT_MIN, pre_xor =0;
// Traverse all input array element
for (int i=0; i<n; i++)
{
// update current prefix xor and insert it into Trie
pre_xor = pre_xor^arr[i];
insert(root, pre_xor);
// Query for current prefix xor in Trie and update
// result if required
result = max(result, query(root, pre_xor));
}
return result;
}
| // C++ program for a Trie based O(n) solution to find max // subarray XOR #include<bits/stdc++.h> using namespace std; // Assumed int size #define INT_SIZE 32 // A Trie Node struct TrieNode { int value; // Only used in leaf nodes TrieNode *arr[2]; }; // Utility function tp create a Trie node TrieNode *newNode() { TrieNode *temp = new TrieNode; temp->value = 0; temp->arr[0] = temp->arr[1] = NULL; return temp; } // Inserts pre_xor to trie with given root void insert(TrieNode *root, int pre_xor) { TrieNode *temp = root; // Start from the msb, insert all bits of // pre_xor into Trie for (int i=INT_SIZE-1; i>=0; i--) { // Find current bit in given prefix bool val = pre_xor & (1<<i); // Create a new node if needed if (temp->arr[val] == NULL) temp->arr[val] = newNode(); temp = temp->arr[val]; } // Store value at leaf node temp->value = pre_xor; } // Finds the maximum XOR ending with last number in // prefix XOR \'pre_xor\' and returns the XOR of this maximum // with pre_xor which is maximum XOR ending with last element // of pre_xor. int query(TrieNode *root, int pre_xor) { TrieNode *temp = root; for (int i=INT_SIZE-1; i>=0; i--) { // Find current bit in given prefix bool val = pre_xor & (1<<i); // Traverse Trie, first look for a // prefix that has opposite bit if (temp->arr[1-val]!=NULL) temp = temp->arr[1-val]; // If there is no prefix with opposite // bit, then look for same bit. else if (temp->arr[val] != NULL) temp = temp->arr[val]; } return pre_xor^(temp->value); } // Returns maximum XOR value of a subarray in arr[0..n-1] int maxSubarrayXOR(int arr[], int n) { // Create a Trie and insert 0 into it TrieNode *root = newNode(); insert(root, 0); // Initialize answer and xor of current prefix int result = INT_MIN, pre_xor =0; // Traverse all input array element for (int i=0; i<n; i++) { // update current prefix xor and insert it into Trie pre_xor = pre_xor^arr[i]; insert(root, pre_xor); // Query for current prefix xor in Trie and update // result if required result = max(result, query(root, pre_xor)); } return result; } |
