Maximum XOR of Two Numbers in an Array LeetCode solution in C++

1
class Solution {
2
 public:
3
  struct TrieNode {
4
    // trie with max 2 child, not taking any bool or 26 size value because no
5
    // need
6
    TrieNode *one;
7
    TrieNode *zero;
8
  };
9
  void insert(TrieNode *root, int n) {
10
    TrieNode *curr = root;
11
    for (int i = 31; i >= 0; i--) {
12
      int bit = (n >> i) & 1; // it will find 31st bit and check it is 1 or 0
13
      if (bit == 0) {
14
        if (curr->zero == nullptr) { // if 0 then we will continue filling on zero side
15
          TrieNode *newNode = new TrieNode();
16
          curr->zero = newNode;
17
        }
18
        curr = curr->zero; // increase cur to next zero position
19
      } else {
20
        // similarly if we get 1
21
        if (curr->one == nullptr) {
22
          TrieNode *newNode = new TrieNode();
23
          curr->one = newNode;
24
        }
25
        curr = curr->one;
26
      }
27
    }
28
  }
29
  int findmax(TrieNode *root, int n) {
30
    TrieNode *curr = root;
31
    int ans = 0;
32
    for (int i = 31; i >= 0; i--) {
33
      int bit = (n >> i) & 1;
34
      if (bit == 1) {
35
        if (curr->zero != nullptr) { // finding complement , if find 1 then we
36
                                     // will check on zero side
37
          ans += (1 << i);           // push values in ans
38
          curr = curr->zero;
39
        } else {
40
          curr = curr->one; // if we don't get then go to one's side
41
        }
42
      } else {
43
        // similarly on zero side if we get 0 then we will check on 1 s side
44
        if (curr->one != nullptr) {
45
          ans += (1 << i);
46
          curr = curr->one;
47
        } else {
48
          curr = curr->zero;
49
        }
50
      }
51
    }
52
    return ans;
53
  }
54

55
  int findMaximumXOR(vector<int> &nums) {
56
    int n = nums.size();
57
    TrieNode *root = new TrieNode();
58
    int ans = 0;
59
    for (int i = 0; i < n; i++) {
60
      insert(root, nums[i]); // it will make trie by inserting values
61
    }
62
    for (int i = 1; i < n; i++) {
63
      ans = max(ans, findmax(root, nums[i])); // find the necessary complementory
64
                                              // values and maximum store
65
    }
66
    return ans;
67
  }
68
};