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; } }