<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 Solution:
    def countPairs(self, nums: List[int], low: int, high: int) -> int:
        pass























class Solution:
    def countPairs(self, nums: List[int], low: int, high: int) -> int:
        cnt = 0
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if low <= nums[i] ^ nums[j] <= high:
                    cnt += 1
        return cnt















from typing import List

class TrieNode:
    def __init__(self):
        self.children = [None, None]  # Represents two branches for 0 and 1
        self.count = 0  # Number of numbers passing through this node

class Solution:
    def countPairs(self, nums: List[int], low: int, high: int) -> int:
        def insert(num: int) -> None:
            node = root
            for i in range(15, -1, -1):  # Assume numbers are 16-bit integers
                bit = (num >> i) & 1
                if not node.children[bit]:
                    node.children[bit] = TrieNode()
                node = node.children[bit]
                node.count += 1
        
        def count_less_than(num: int, limit: int) -> int:
            node = root
            count = 0
            for i in range(15, -1, -1):
                if not node:
                    break
                num_bit = (num >> i) & 1
                limit_bit = (limit >> i) & 1
                
                if limit_bit == 1:
                    # Add all numbers with the current bit as `num_bit`
                    if node.children[num_bit]:
                        count += node.children[num_bit].count
                    # Move to the next potential branch (opposite bit)
                    node = node.children[1 - num_bit]
                else:
                    # Continue in the current branch
                    node = node.children[num_bit]
            return count
        
        # Initialize the trie root
        root = TrieNode()
        
        # Function to count pairs with XOR less than a given value
        def count_pairs_with_xor_less_than(limit: int) -> int:
            count = 0
            for num in nums:
                count += count_less_than(num, limit)
                insert(num)
            return count

        # Calculate the number of pairs within the desired range
        total_pairs_high = count_pairs_with_xor_less_than(high + 1)
        # Reset the Trie for the next calculation
        root = TrieNode()
        total_pairs_low = count_pairs_with_xor_less_than(low)

        return total_pairs_high - total_pairs_low






















class TrieNode:
    def __init__(self):
        self.children = [None, None]
        self.visited = 0

class Solution:
    def countPairs(self, nums: List[int], low: int, high: int) -> int:

        def insert(num):
            node = root
            for idx in range(15, -1, -1):
                b = (num >> idx) & 1
                if not node.children[b]:
                    node.children[b] = TrieNode()
                node = node.children[b]
                node.visited += 1

        
        def count_less_than(num, limit):
            
            cnt = 0
            node = root
            for idx in range(15, -1, -1):
                if not node:
                    break
                num_bit = (num >> idx) & 1
                limit_bit = (limit >> idx) & 1

                if limit_bit:
                    # count same bit as num_bit and move to 1-num_bit
                    if node.children[num_bit]:
                        cnt += node.children[num_bit].visited
                    node = node.children[1-num_bit]
                else:
                    # move to the same num_bit
                    node = node.children[num_bit]
            return cnt



        def count_pairs_with_xor_less_than(limit: int) -> int:
            cnt = 0
            for num in nums:
                cnt += count_less_than(num, limit)
                insert(num)
            return cnt

        root = TrieNode()
        total_pairs_high = count_pairs_with_xor_less_than(high + 1)
        root = TrieNode()
        total_pairs_low = count_pairs_with_xor_less_than(low)
        return total_pairs_high - total_pairs_low

















class TrieNode:
    def __init__(self):
        self.children = [None, None]
        self.visited = 0


class Solution:
    def countPairs(self, nums: List[int], low: int, high: int) -> int:

        def insert(num):
            node = root
            for i in range(15, -1, -1):
                b = (num >> i) & 1
                if not node.children[b]:
                    node.children[b] = TrieNode()
                node = node.children[b]
                node.visited += 1
        
        def count_less_than_equal(num, limit):
            cnt = 0
            node = root
            for i in range(15, -1, -1):
                if not node:
                    break
                num_bit = (num >> i) & 1
                limit_bit = (limit >> i) & 1
                
                if limit_bit:
                    if node.children[num_bit]:
                        cnt += node.children[num_bit].visited
                    node = node.children[1-num_bit]
                else:
                    node = node.children[num_bit]
            return cnt

        def count_and_insert(limit):
            cnt = 0
            for num in nums:
                node = root
                cnt += count_less_than_equal(num, limit)
                insert(num)
            return cnt

        root = TrieNode()
        cnt1 = count_and_insert(high+1)
        root = TrieNode()
        cnt2 = count_and_insert(low)
        return cnt1 - cnt2
















class TrieNode:
    def __init__(self):
        self.children = [None, None]
        self.visited = 0

class Solution:
    def countPairs(self, nums: List[int], low: int, high: int) -> int:
        def insert(num):
            node = root
            for i in range(15, -1, -1):
                b = (num >> i) & 1
                if not node.children[b]:
                    node.children[b] = TrieNode()
                node = node.children[b]
                node.visited += 1
        
        def count_and_insert(nums, limit):
            cnt = 0
            for num in nums:
                cnt += count_less_than_equal(num, limit)
                insert(num)
            return cnt

        def count_less_than_equal(num, limit):
            node = root
            cnt = 0
            for i in range(15, -1, -1):
                if not node:
                    break
                num_bit = (num >> i) & 1
                limit_bit = (limit >> i) & 1

                if limit_bit:
                    if node.children[num_bit]:
                        cnt += node.children[num_bit].visited
                    node = node.children[1 - num_bit]
                else:
                    node = node.children[num_bit]
            return cnt

        root = TrieNode()
        cnt1 = count_and_insert(nums, high+1)
        root = TrieNode()
        cnt2 = count_and_insert(nums, low)
        return cnt1 - cnt2
24900