Count Pairs With XOR in a Range LeetCode solution in JavaScript

1
var countPairs = function (nums, low, high) {
2
  function insert(num) {
3
    var node = root;
4
    for (i = 14; i >= 0; i--) {
5
      var bit = (num >> i) & 1;
6
      if (!node.children[bit]) {
7
        node.children[bit] = new TrieNode();
8
      }
9
      node.children[bit].cnt += 1;
10
      node = node.children[bit];
11
    }
12
  }
13
  function countSmallerNums(num, limit) {
14
    var cnt = 0;
15
    // count pairs with num strictly smaller than limit
16
    var node = root;
17
    for (i = 14; i >= 0 && node; i--) {
18
      var lbit = (limit >> i) & 1;
19
      var nbit = (num >> i) & 1;
20
      if (lbit === 1) {
21
        // we can decrease on 1 bit
22
        if (node.children[nbit]) {
23
          cnt += node.children[nbit].cnt;
24
        }
25
        // go to another way to find next bit count
26
        node = node.children[1 - nbit];
27
      } else {
28
        // cannot increase the lbit === 0,
29
        // find the same Nbit to XOR to be '0'
30
        node = node.children[nbit];
31
      }
32
    }
33
    return cnt;
34
  }
35
  // starts here
36
  var root = new TrieNode();
37
  var res = 0;
38
  for (var num of nums) {
39
    res += countSmallerNums(num, high + 1) - countSmallerNums(num, low);
40
    insert(num);
41
  }
42
  return res;
43
};
44

45
class TrieNode {
46
  constructor() {
47
    this.cnt = 0;
48
    this.children = new Array(2).fill(null);
49
  }
50
}