Maximum XOR With an Element From Array LeetCode solution in C++

1
struct Trie {
2
  Trie *z;
3
  Trie *o;
4
  Trie() {
5
    z = NULL;
6
    o = NULL;
7
  }
8
};
9

10
class Solution {
11
 public:
12
  Trie *insert(Trie *node, int k, int num) {
13
    if (node == NULL) {
14
      node = new Trie();
15
    }
16
    if (k < 0) return node;
17
    if (((num >> k) & 1) == 1) {
18
      node->o = insert(node->o, k - 1, num);
19
    } else {
20
      node->z = insert(node->z, k - 1, num);
21
    }
22
    return node;
23
  }
24

25
  int getmax(Trie *node, int k, int num) {
26
    if (k < 0) return 0;
27
    int res = 0;
28
    bool bit = ((num >> k) & 1);
29
    if (bit == 1) {
30
      if (node->z) {
31
        res = pow(2, k) + getmax(node->z, k - 1, num);
32
      } else {
33
        res = getmax(node->o, k - 1, num);
34
      }
35
    } else {
36
      if (node->o) {
37
        res = pow(2, k) + getmax(node->o, k - 1, num);
38
      } else {
39
        res = getmax(node->z, k - 1, num);
40
      }
41
    }
42
    return res;
43
  }
44

45
  vector<int> maximizeXor(vector<int> &nums, vector<vector<int>> &queries) {
46
    int n = nums.size();
47
    int m = queries.size();
48
    vector<int> ans(m, -1);
49
    vector<pair<pair<int, int>, int>> q;
50
    for (int i = 0; i < m; i++) {
51
      q.push_back({{queries[i][0], queries[i][1]}, i});
52
    }
53
    sort(q.begin(), q.end(), [](pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
54
      return a.first.second < b.first.second;
55
    });
56

57
    sort(nums.begin(), nums.end());
58

59
    int j = 0;
60

61
    Trie *root = new Trie();
62

63
    for (int i = 0; i < m; i++) {
64
      pair<pair<int, int>, int> p = q[i];
65
      int num = p.first.first;
66
      int lim = p.first.second;
67
      int idx = p.second;
68

69
      while (j < n && nums[j] <= lim) {
70
        root = insert(root, 31, nums[j]);
71
        j++;
72
      }
73

74
      if (j > 0) {
75
        ans[idx] = getmax(root, 31, num);
76
      }
77
    }
78

79
    return ans;
80
  }
81
};