<p>Given a <strong>(0-indexed)</strong> integer array <code>nums</code> and two integers <code>low</code> and <code>high</code>, return <em>the number of <strong>nice pairs</strong></em>.</p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,4,2,7], low = 2, high = 6
<strong>Output:</strong> 6
<strong>Explanation:</strong> 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
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [9,8,4,2,1], low = 5, high = 14
<strong>Output:</strong> 8
<strong>Explanation:</strong> 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</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= low &lt;= high &lt;= 2 * 10<sup>4</sup></code></li>
</ul>
class Node:
    def __init__(self):
        self.countOfNumbers = 0 # the count of numbers in this nodes subtree
        self.children = {} # maps a 0 or 1 to a child Node
    def __str__(self, level=0):
        result = "  " * level + f"Node(count={self.countOfNumbers})\n"
        for bit, child in self.children.items():
            result += "  " * (level + 1) + f"Bit {bit}:\n"
            result += child.__str__(level + 2)
        return result

class BitTrie:
    def __init__(self, BITS=32):
        self.root = Node()
        self.BITS = BITS

    def __str__(self):
        return self.root.__str__()

    # Inserts a number into the Trie, O(BITS) time
    def insert(self, num):
        curr = self.root
        for bitOffset in range(self.BITS - 1, -1, -1):
            bit = (num >> bitOffset) & 1
            if bit not in curr.children:
                curr.children[bit] = Node()
            curr.countOfNumbers += 1
            curr = curr.children[bit]
        # add the count for the leaf node also
        curr.countOfNumbers += 1
    
    # Tells us how many numbers in the Trie, when XORd with `valToBeXord` are <= threshold, where threshold >= 0. O(BITS) time
    def countNumbersLTEVal(self, valToBeXord, threshold):
        if not self.root.children:
            return 0

        # Helper function that gets the answer for this sub problem
        def dfs(parentTrieNode, bitOffset):
            # Basically if we have a full match, so our number XORd with another number in the trie exactly equaled the threshold
            if bitOffset < 0:
                return parentTrieNode.countOfNumbers

            limitBit = (threshold >> bitOffset) & 1
            valueBit = (valToBeXord >> bitOffset) & 1

            resHere = 0

            # CASE 1: limit bit is 0, our value bit is 0, we recurse to 0 subtree
            if limitBit == 0 and valueBit == 0 and 0 in parentTrieNode.children:
                resHere += dfs(parentTrieNode.children[0], bitOffset - 1)

            # CASE 2: limit bit is 0, our value bit is 1, we recurse to 1 subtree
            if limitBit == 0 and valueBit == 1 and 1 in parentTrieNode.children:
                resHere += dfs(parentTrieNode.children[1], bitOffset - 1)
            
            # CASE 3: limit bit is 1, our value bit is 0, w can take the 0 subtree, and recurse to the 1 subtree
            if limitBit == 1 and valueBit == 0:
                if 0 in parentTrieNode.children:
                    resHere += parentTrieNode.children[0].countOfNumbers
                if 1 in parentTrieNode.children:
                    resHere += dfs(parentTrieNode.children[1], bitOffset - 1)
            
            # CASE 4: limit bit is 1, our value bit is 1, we can take the 1 subtree, and recurse to the 0 subtree
            if limitBit == 1 and valueBit == 1:
                if 1 in parentTrieNode.children:
                    resHere += parentTrieNode.children[1].countOfNumbers
                if 0 in parentTrieNode.children:
                    resHere += dfs(parentTrieNode.children[0], bitOffset - 1)
            
            return resHere

        return dfs(self.root, self.BITS - 1)

# 0 0 1
# 0 1 0

# number
# 0 0 1

# candidates
# 1 0 0
# 1 1 1

# HIGH
# 1 1 0

class Solution:
    def countPairs(self, nums: List[int], low: int, high: int) -> int:
        BITS = math.ceil(math.log2(max(max(nums), high))) + 1
        t = BitTrie(BITS)
        res = 0    
        
        # calculate number <= high
        for num in nums:
            t.insert(num)
            res += t.countNumbersLTEVal(num, high)     
            res -= t.countNumbersLTEVal(num, low - 1)       
        
        return res

27700