# XOR Maximum

Trie

Medium

#### Problem Statement :

Given array of `N` numbers, we need to find the maximum xor between any pair of the numbers.

See original problem statement here #### Introduction :

Idea is to store the numbers in their binary representation. Let's consider the `X` in bitwise and from the highest bit of `X=>i` to lowest bit `0`. The remaining numbers can be divided into two set one with set(1) bit at the bit position i and the other with unset(0) bit at the bit position `i`, if the bit in the ith position of `X` is set then we would consider all the numbers with unset bit and neglect the other half similar for when ith bit in the `X` being unset.

#### Description:

We will use trie to solve this problem by learning the best online programming courses.
A Trie is a special data structure used to store strings that can be visualized like a graph. It consists of nodes and edges. Each node consists of atmost `26` children and edges connect each parent node to its children. These `26` node pointers is for `26` letters of the English alphabet. A separate edge is maintained for every edge.
We will build a trie with height being most significant bit of the largest number. To search in the Trie, we start with the first diverging point in the trie. For example, given [9, 10, 14, 13], or [1001, 1010, 1110, 1101], we start with the second bit, because all numbers is set on the first bit. The trie is also a balanced one, because each number is represented by a path whose length is equal to the trie height. For example, given [3, 10, 5, 25, 2, 8], the numbers are represented by 00011, 01010, 00101, 11001, 00010, 01000 in the trie.
Now, the starting point is the first trie node having two diverging sub-tries on the left and on the right. We try to go opposite branches(0 versus 1) in the respective sub-tries whenever possible. Sometimes we have two choices and we try them both, and sometimes we are forced to go in the same branch because that's the only option.

#### insert():

• iterate for every integer `i` in array, `arr[]`, and store the number in its binary representation.
• check if the number (0 or 1) previously being inserted,
• if not, make a new tree node for this number and add it as the children of the root.
• if it is already present, make the child node as parent and do the same with the remaining bits .
• After inserting the last bitr node of `i` in tree , update the weight of the last bit of `i`, `(temp->value = key)`.

#### maxXOR():

• iterate for every integer `i` in array, `arr[]`,
• for every `i`, find the current bit in the prefix,
• if there is no same bit then look for opposite bits
• else, look for prefix which has same bits.
• return xor value of maximum bit difference value so we get maximum xor value .
• Update xor value for every `i`.

#### Complexity Analysis :

We are inserting all the elements of array of size `N`, lets say. Also we are searching for `N` intereger values of the array at a time for a single query.
Space complexity of this data structure would be `O(2*N)`, where `N` is the length of array.

## Solutions:

```#include <stdio.h>
#include<stdlib.h>
#include<math.h>
#include<stdio.h>

#define INT_MIN -9999

typedef struct TrieNode{
struct TrieNode* left;
struct TrieNode* right;
};

void insert(struct TrieNode* cur, int n)
{
for(int i=31;i>=0;i--)
{
int b = (n>>i)&1;
if(b)
{
if(!cur->right)
cur->right = (struct TrieNode*)malloc(sizeof(struct TrieNode));
cur = cur->right;
}
else
{
if(!cur->left)
cur->left = (struct TrieNode*)malloc(sizeof(struct TrieNode));
cur = cur->left;
}
}
}
int find(struct TrieNode* head, int nums[],int n)
{
int max = INT_MIN;
for(int i=0;i<n;i++)
{
int cur = 0;
for(int j=31;j>=0;j--)
{
int b = (nums[i]>>j)&1;
if(b)
{
if(tmp->left)
{
cur += pow(2,j);
tmp = tmp->left;
}
else
tmp = tmp->right;
}
else
{
if(tmp->right)
{
cur += pow(2,j);
tmp = tmp->right;
}
else
tmp = tmp->left;
}
}
if(max<cur) max = cur;
}
return max;
}
int findMaximumXOR(int nums[],int n) {
struct TrieNode* head = (struct TrieNode*)malloc(sizeof(struct TrieNode));
for(int i=0;i<n;i++)
if(res == INT_MIN) return 0;
return res;
}

int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
int num[n];
for(int i=0;i<n;i++)
{
scanf("%d",&num[i]);
}
printf("%d\n",findMaximumXOR(num,n));
}
}
```
```#include<bits/stdc++.h>
using namespace std;

struct TrieNode{
TrieNode* left;
TrieNode* right;
};
void insert(TrieNode* cur, int n)
{
for(int i=31;i>=0;i--)
{
int b = (n>>i)&1;
if(b)
{
if(!cur->right)
cur->right = new TrieNode();
cur = cur->right;
}
else
{
if(!cur->left)
cur->left = new TrieNode();
cur = cur->left;
}
}
}
int find(TrieNode* head, int nums[],int n)
{
int max = INT_MIN;
for(int i=0;i<n;i++)
{
int cur = 0;
for(int j=31;j>=0;j--)
{
int b = (nums[i]>>j)&1;
if(b)
{
if(tmp->left)
{
cur += pow(2,j);
tmp = tmp->left;
}
else
tmp = tmp->right;
}
else
{
if(tmp->right)
{
cur += pow(2,j);
tmp = tmp->right;
}
else
tmp = tmp->left;
}
}
if(max<cur) max = cur;
}
return max;
}

int findMaximumXOR(int nums[],int n) {
for(int i=0;i<n;i++)

if(res == INT_MIN) return 0;
return res;
}

int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int num[n];
for(int i=0;i<n;i++)
{
cin>>num[i];
}
cout<<findMaximumXOR(num,n)<<endl;
}
}
```
```import java.util.*;

class Main
{
static final int INT_SIZE = 32;

// A Trie Node
static class TrieNode {
int value;
TrieNode[] Child = new TrieNode;

public TrieNode()
{
value = 0;
Child = null;
Child = null;
}
}
static TrieNode root;

static void insert(int key)
{
TrieNode temp = root;

for (int i = INT_SIZE - 1; i >= 0; i--) {

int current_bit = (key & (1 << i)) >= 1 ? 1 : 0;

if (temp != null && temp.Child[current_bit] == null)
temp.Child[current_bit] = new TrieNode();

temp = temp.Child[current_bit];
}

temp.value = key;
}

static int maxXORUtil(int key)
{
TrieNode temp = root;

for (int i = INT_SIZE - 1; i >= 0; i--)
{
// Find current bit in given prefix
int current_bit = (key & (1 << i)) >= 1 ? 1 : 0;

if (temp.Child[1-current_bit] != null)
temp = temp.Child[1-current_bit];

else if (temp.Child[ current_bit] != null)
temp = temp.Child[ current_bit];
}

return key ^ temp.value;
}

static int maxXOR(int arr[], int n)
{
int max_xor = Integer.MIN_VALUE;
root = new TrieNode();
insert(arr);

for (int i = 1; i < n; i++) {

max_xor = Math.max(max_xor, maxXORUtil(arr[i]));

insert(arr[i]);
}
return max_xor;
}

public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0)
{
int n = sc.nextInt();
int []arr = new int[n];
for(int i=0;i<n;i++)
arr[i]= sc.nextInt();
System.out.println(maxXOR(arr, n));
}
}
}
```

More references to this problem