Scribd
Upload
15 views3 pages

ADS Lab Week 13

This document describes a program to find the maximum XOR of two elements in an integer array using a Trie data structure. It defines a TrieNode struct with child nodes and a value. A function inserts XOR prefixes into the Trie and a query function finds the maximum XOR ending with a given prefix by traversing the Trie. The maxSubarrayXOR function inserts all element XOR prefixes, queries the Trie to update the maximum XOR result, and returns the overall maximum XOR value.

Uploaded by

Kesava
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
15 views3 pages

ADS Lab Week 13

This document describes a program to find the maximum XOR of two elements in an integer array using a Trie data structure. It defines a TrieNode struct with child nodes and a value. A function inserts XOR prefixes into the Trie and a query function finds the maximum XOR ending with a given prefix by traversing the Trie. The maxSubarrayXOR function inserts all element XOR prefixes, queries the Trie to update the maximum XOR result, and returns the overall maximum XOR value.

Uploaded by

Kesava
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

AIM: Given an array of integers, with Trie structure find out two elements whose XOR is

maximum.

Program:

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
// Assumed int size
#define INT_SIZE 32
// A Trie Node
struct TrieNode
{
int value; // Only used in leaf nodes
struct TrieNode *arr[2];
};
// Utility function tp create a Trie node
struct TrieNode *newNode()
{
struct TrieNode *temp =malloc(sizeof(struct TrieNode));
temp->value = 0;
temp->arr[0] = temp->arr[1] = NULL;
return temp;
}
// Inserts pre_xor to trie with given root
void insert(struct TrieNode *root, int pre_xor)
{
struct 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(struct TrieNode *root, int pre_xor)
{
struct 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);
}

int max(int result,int x)


{

return (result > x )?result:x;


}

// 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
struct TrieNode *root = newNode();
insert(root, 0);

// Initialize answer and xor of current prefix


int result = INT_SIZE;
int 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
int result = max(result, query(root, pre_xor));
}
return result;
}

// Driver program to test above functions


int main()
{
int arr[] = {8, 1, 2, 12};
int n = sizeof(arr)/sizeof(arr[0]); int result;
printf("Max subarray XOR is %d", result);
return 0;

Output:

Max subarray XOR is 21870

You might also like