# Min XOR Value

Given an array of N integers, find the pair of integers in the array which have minimum XOR value. Report the minimum XOR value.

Examples :
Input
0 2 5 7
Output
2 (0 XOR 2)
Input
0 4 7 9
Output
3 (4 XOR 7)

Constraints:
2 <= N <= 100 000
0 <= A[i] <= 1 000 000 000

Method1:

We sort the array and then compare the neighbors because the min value can only exist between neighbors.

Solution1:

Time: O(nlogn)
Space: O(1)

public class Solution {
public int findMinXor(ArrayList<Integer> A) {
Collections.sort(A);
int min = Integer.MAX_VALUE;
for (int i = 0; i < A.size() - 1; i ++) {
int a = A.get(i);
int b = A.get(i + 1);
min = Math.min(min, a ^ b);
}
return min;
}
}

Method2:

Use Trie.

Solution2:

Time: O(n)
Space: O(n)

public class Solution {
static class TrieNode {
int value;
TrieNode[] children = new TrieNode[2];

public TrieNode() {
value = 0;
children[0] = null;
children[1] = null;
}
}

static class Trie {
TrieNode root;

public Trie() {
root = new TrieNode();
}

public void insert(int key) {
TrieNode curr = root;
for (int i = 31; i >= 0; i --) {
int currentBit = (key & (1 << i)) >= 1 ? 1 : 0;
if (curr.children[currentBit] == null) {
curr.children[currentBit] = new TrieNode();
}
curr = curr.children[currentBit];
}
curr.value = key;
}

public int minXOR(int key) {
TrieNode curr = root;
for (int i = 31; i >= 0; i --) {
int currentBit = (key & (1 << i)) >= 1 ? 1 : 0;
if (curr.children[currentBit] != null) {
curr = curr.children[currentBit];
} else if (curr.children[1 - currentBit] != null) {
curr = curr.children[1 - currentBit];
}
}
return curr.value ^ key;
}
}

public int findMinXor(ArrayList<Integer> A) {
Trie trie = new Trie();
trie.insert(A.get(0));
int minXor = Integer.MAX_VALUE;
for (int i = 1; i < A.size(); i ++) {
minXor = Math.min(minXor, trie.minXOR(A.get(i)));
trie.insert(A.get(i));
}
return minXor;
}
}