Given a (0-indexed) integer array nums and two integers low and high, return the number of nice pairs.

A nice pair is a pair (i, j) where 0 &lt;= i &lt; j &lt; nums.length and low &lt;= (nums[i] XOR nums[j]) &lt;= high.

&nbsp;
Example 1:

Input: nums = [1,4,2,7], low = 2, high = 6
Output: 6
Explanation: All nice pairs (i, j) are as follows:
    - (0, 1): nums[0] XOR nums[1] = 5 
    - (0, 2): nums[0] XOR nums[2] = 3
    - (0, 3): nums[0] XOR nums[3] = 6
    - (1, 2): nums[1] XOR nums[2] = 6
    - (1, 3): nums[1] XOR nums[3] = 3
    - (2, 3): nums[2] XOR nums[3] = 5


Example 2:

Input: nums = [9,8,4,2,1], low = 5, high = 14
Output: 8
Explanation: All nice pairs (i, j) are as follows:
​​​​​    - (0, 2): nums[0] XOR nums[2] = 13
&nbsp;   - (0, 3): nums[0] XOR nums[3] = 11
&nbsp;   - (0, 4): nums[0] XOR nums[4] = 8
&nbsp;   - (1, 2): nums[1] XOR nums[2] = 12
&nbsp;   - (1, 3): nums[1] XOR nums[3] = 10
&nbsp;   - (1, 4): nums[1] XOR nums[4] = 9
&nbsp;   - (2, 3): nums[2] XOR nums[3] = 6
&nbsp;   - (2, 4): nums[2] XOR nums[4] = 5

&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 2 * 104
	1 &lt;= nums[i] &lt;= 2 * 104
	1 &lt;= low &lt;= high &lt;= 2 * 104

from collections import defaultdict

class TrieNode:
    def __init__(self):
        self.nodes = defaultdict(TrieNode)
        self.cnt = 0

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, val):
        cur = self.root
        for i in reversed(range(15)):
            bit = val >> i & 1
            cur.nodes[bit].cnt += 1
            cur = cur.nodes[bit]

    def count(self, val, high):
        res = 0
        cur = self.root
        for i in reversed(range(15)):
            if not cur:
                break
            bit = val >> i & 1
            cmp = high >> i & 1
            if cmp:
                res += cur.nodes[bit].cnt
                cur = cur.nodes[1^bit]
            else:
                cur = cur.nodes[bit]
        return res

class Solution:
    def countPairs(self, nums: List[int], low: int, high: int) -> int:
        trie = Trie()
        res = 0
        for num in nums:
            res += trie.count(num, high + 1) - trie.count(num, low)
            trie.insert(num)

        return res
class Solution {
    public int countPairs(int[] nums, int low, int high) {
        Trie trie=new Trie();
        int cnt=0;
        for(int i=nums.length-1;i>=0;i--){
            // count all the element whose xor is less the low
            int cnt1=trie.maxXor(nums[i],low);
            // count all the element whose xor is less the high+1
            int cnt2=trie.maxXor(nums[i],high+1);
            trie.add(nums[i]);
            cnt+=cnt2-cnt1;
        }
        return cnt;
    }
}
class Trie{
    private Node root;
    Trie(){
        root=new Node();
    }
    public void add(int x){
        Node cur=root;
        for(int i=31;i>=0;i--){
            int bit=(x>>i)&1;
            if(!cur.contains(bit)){
                cur.put(bit);
            }
            cur.inc(bit);
            cur=cur.get(bit);
        }
    }
    public int maxXor(int x,int limit){
        int low_cnt=0;
        Node cur=root;
        for(int i=31;i>=0 && cur!=null;i--){
            int bit=(x>>i)&(1);
            int req=(limit>>i)&1;
            if(req==1){
                if(cur.contains(bit)){
                    low_cnt+=cur.get(bit).cnt;
                }
                cur=cur.get(1-bit);
            }else{
                cur=cur.get(bit);
            }

        }
        return low_cnt;

    }
}
class Node{
    private Node links[];
    int cnt;
    Node(){
        links=new Node[2];
        cnt=0;
    }
    public void put(int bit){
        links[bit]=new Node();
    }
    public Node get(int bit){
        return links[bit];
    }
    public boolean contains(int bit){
        return links[bit]!=null;
    }
    public void inc(int bit){
        links[bit].cnt++;
    }
}
struct Node {
    Node* arr[2];
    int count = 0;

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

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

    Node* getNext(int bitNo) {
        return arr[bitNo];
    }

    int getCount(int bitNo) {
        return arr[bitNo]->count;
    }

    void setCount(int bitNo) {
        arr[bitNo]->count++;
    }
};

class Solution {
public:

    Node* root = new Node();

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

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

            if(!temp->contains(bitVal)) {
                temp->put(bitVal, new Node());
            }
            temp->setCount(bitVal);
            temp = temp->getNext(bitVal);
        }
    }

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

        int cntPairs = 0;

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

            if(bit_k) {
                if(temp->contains(bit_num)) {
                    cntPairs += temp->getCount(bit_num);
                }
                if(temp->contains(1 - bit_num)) {
                    temp = temp->getNext(1 - bit_num);
                }
                else break;
            }
            else if(temp->contains(bit_num)) {
                temp = temp->getNext(bit_num);
            }
            else {
                break;
            }
        }
        return cntPairs;
    }

    int countPairs(vector<int>& nums, int low, int high) {

        int n = nums.size();
        int cnt = 0;
        for(int i=0; i<n; i++) {
            cnt += getPairs(nums[i], high+1) - getPairs(nums[i], low);
            insert(nums[i]);
        }
        return cnt;
    }
};
var countPairs = function(nums, low, high) {
    function insert(num){
        var node = root;
        for(i = 14; i>=0; i--)
        {
            var bit = (num >> i) & 1;
            if(!node.children[bit])
            {
                node.children[bit] = new TrieNode();
            }
            node.children[bit].cnt += 1;
            node = node.children[bit];
        }
    }
    function countSmallerNums(num, limit)
    {
        var cnt = 0;
        // count pairs with num strictly smaller than limit
        var node = root;
        for(i = 14; i>=0 && node; i--)
        {
            var lbit = (limit>>i) & 1;
            var nbit = (num >> i) & 1;
            if(lbit===1)
            {
                // we can decrease on 1 bit
                if(node.children[nbit])
                {
                     cnt += node.children[nbit].cnt;
                }
                // go to another way to find next bit count
                node = node.children[1-nbit];
            }
            else
            {
                // cannot increase the lbit === 0,
                // find the same Nbit to XOR to be '0'
                node = node.children[nbit];
            }
        }
        return cnt;
    }
    // starts here
    var root = new TrieNode();
    var res =0;
    for(var num of nums)
    {
        res += countSmallerNums(num, high+1) -  countSmallerNums(num, low);
        insert(num);
    }
    return res;
};

class TrieNode{
    constructor()
    {
        this.cnt = 0;
        this.children = new Array(2).fill(null);
    }
}
Count Pairs With XOR in a Range