Maximum XOR of Two Numbers in an Array LeetCode solution in Java

1
class Node {
2
  Node[] links = new Node[2];
3

4
  public Node() {}
5

6
  boolean containsKey(int ind) {
7
    return links[ind] != null;
8
  }
9

10
  Node get(int ind) {
11
    return links[ind];
12
  }
13

14
  void put(int ind, Node node) {
15
    links[ind] = node;
16
  }
17
}
18

19
class Trie {
20
  private static Node root;
21

22
  public Trie() {
23
    root = new Node();
24
  }
25

26
  public static void insert(int num) {
27
    Node node = root;
28
    for (int i = 31; i >= 0; i--) {
29
      int bit = (num >> i) & 1;
30
      if (!node.containsKey(bit)) {
31
        node.put(bit, new Node());
32
      }
33
      node = node.get(bit);
34
    }
35
  }
36

37
  public static int getMax(int num) {
38
    Node node = root;
39
    int maxNum = 0;
40

41
    for (int i = 31; i >= 0; i--) {
42
      int bit = (num >> i) & 1;
43
      if (node.containsKey(1 - bit)) {
44
        maxNum = maxNum | (1 << i);
45
        node = node.get(1 - bit);
46
      } else {
47
        node = node.get(bit);
48
      }
49
    }
50
    return maxNum;
51
  }
52
}
53

54
class Solution {
55
  public int findMaximumXOR(int[] nums) {
56
    Trie trie = new Trie();
57

58
    for (int i = 0; i < nums.length; i++) {
59
      trie.insert(nums[i]);
60
    }
61

62
    int maxi = 0;
63
    for (int i = 0; i < nums.length; i++) {
64
      maxi = Math.max(maxi, trie.getMax(nums[i]));
65
    }
66
    return maxi;
67
  }
68
}