Count Pairs With XOR in a Range LeetCode solution in C++

1
struct Node {
2
  Node *arr[2];
3
  int count = 0;
4

5
  bool contains(int bitNo) {
6
    return arr[bitNo] != NULL;
7
  }
8

9
  void put(int bitNo, Node *newNode) {
10
    arr[bitNo] = newNode;
11
  }
12

13
  Node *getNext(int bitNo) {
14
    return arr[bitNo];
15
  }
16

17
  int getCount(int bitNo) {
18
    return arr[bitNo]->count;
19
  }
20

21
  void setCount(int bitNo) {
22
    arr[bitNo]->count++;
23
  }
24
};
25

26
class Solution {
27
 public:
28
  Node *root = new Node();
29

30
  void insert(int num) {
31
    Node *temp = root;
32

33
    for (int bit = 15; bit >= 0; bit--) {
34
      int bitVal = (bool)(num & (1 << bit));
35

36
      if (!temp->contains(bitVal)) {
37
        temp->put(bitVal, new Node());
38
      }
39
      temp->setCount(bitVal);
40
      temp = temp->getNext(bitVal);
41
    }
42
  }
43

44
  int getPairs(int num, int k) {
45
    Node *temp = root;
46

47
    int cntPairs = 0;
48

49
    for (int bit = 15; bit >= 0 && temp; bit--) {
50
      int bit_num = (bool)(num & (1 << bit));
51
      int bit_k = (bool)(k & (1 << bit));
52

53
      if (bit_k) {
54
        if (temp->contains(bit_num)) {
55
          cntPairs += temp->getCount(bit_num);
56
        }
57
        if (temp->contains(1 - bit_num)) {
58
          temp = temp->getNext(1 - bit_num);
59
        } else
60
          break;
61
      } else if (temp->contains(bit_num)) {
62
        temp = temp->getNext(bit_num);
63
      } else {
64
        break;
65
      }
66
    }
67
    return cntPairs;
68
  }
69

70
  int countPairs(vector<int> &nums, int low, int high) {
71
    int n = nums.size();
72
    int cnt = 0;
73
    for (int i = 0; i < n; i++) {
74
      cnt += getPairs(nums[i], high + 1) - getPairs(nums[i], low);
75
      insert(nums[i]);
76
    }
77
    return cnt;
78
  }
79
};