<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:
                    '''
                    limit_bit=1일때, trie node에서 0으로 가야할까, 1로 가야할까. 
                    지금 num_bit를 0이라고 가정해보자. trie node에서 0으로 가면, num_bit^trie_bit = 0^0 = 0이 된다. 
                    limit_bit인 1보다 작은값인 0이 되기 때문에, 해당 0으로 연결된 모든 trie node들은 limit보다 작게되어서 cnt에 추가하면 됨. 
                    그리고 node는 1로 가서 추가적인 탐색을 벌이면 된다. 
                    여기서 num_bit을 0이라고 가정했는데, 1도 역시 마찬가지다. 
                    일반화 시킨다면, 지금 num_bit에 대해서, trie_bit이 num_bit과 동일한 값은 모두 cnt에 추가시키고, 
                    1 - num_bit로 움직여서 추가적인 탐색을 진행하면 된다는 소리임. 
                    '''
                    if node.children[num_bit]:
                        cnt += node.children[num_bit].visited
                    node = node.children[1 - num_bit]
                else:
                    '''
                    먄약 limit_bit이 0이라면?
                    num_bit과 다른 trie_bit은 num_bit^trie_bit = 1이 되어서 limit_bit보다 크기때문에, cnt에 추가할 수 없음. 
                    따라서 num_bit과 동일한 값이 되는 trie_bit로 가야함. 
                    '''
                    node = node.children[num_bit]
            return cnt

        root = TrieNode()
        cnt1 = count_and_insert(nums, high+1)
        root = TrieNode()
        cnt2 = count_and_insert(nums, low)
        '''
        root를 왜 초기화 하나?
        count_and_insert로 인하여 생성되는 trie는 low, high에 대해서 동일함. 
        단지, 문제에서 i<j 조건이 있는데, trie를 high를 다룰 때, 모두 만들어 둔것을 low에서 또 쓰게되면, 
        i<j 조건을 만족하지 못하니까 새로 만드는것임. 
        '''
        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):
            # insert num to bit-trie
            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:
                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]

                insert(num)
            return cnt
        
        root = TrieNode()
        cnt1 = count_and_insert(nums, high+1)
        root = TrieNode()
        cnt2 = count_and_insert(nums, 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
        
        # function
        def count_and_insert(nums, limit):
            cnt = 0
            for num in nums:
                node = root
                for i in range(15, -1, -1):
                    if not node:
                        break

                    bit_num = (num >> i) & 1
                    bit_limit = (limit >>i) & 1

                    if bit_limit == 1:
                        if node.children[bit_num]:
                            cnt += node.children[bit_num].visited
                        node = node.children[1-bit_num]
                    else:
                        node = node.children[bit_num]

                insert(num)
            return cnt
    
        root = TrieNode()
        cnt1 = count_and_insert(nums, high+1)
        root = TrieNode()
        cnt2 = count_and_insert(nums, 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:
                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]
                insert(num)
            return cnt
        
        
        root = TrieNode()
        cnt1 = count_and_insert(nums, high+1)
        root = TrieNode()
        cnt2 = count_and_insert(nums, 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:
        '''
        iterate num in nums. 
        count the number of num in the nums[i], where i < j, 
            s.t. nums[i] XOR nums[j] < limit
        '''
        root = TrieNode()

        def insert(num):
            node = root
            for i in range(15, -1, -1):
                num_bit = (num >> i) & 1
                if not node.children[num_bit]:
                    node.children[num_bit] = TrieNode()
                node = node.children[num_bit]
                node.visited += 1
        
        def count_and_insert(nums, limit):
            '''
            count the number of num in the nums[i], where i < j, 
                s.t. nums[i] XOR nums[j] < limit
            ''' 
            cnt = 0
            for num in nums:
                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 == 1:
                        # count all nums[i] that nums[i] XOR num == 0
                        # move to nums[i] that nums[i] XOR num == 1
                        if node.children[num_bit]:
                            cnt += node.children[num_bit].visited
                        node = node.children[1 - num_bit]
                    else:
                        node = node.children[num_bit]
                insert(num)
            return cnt
        
        root = TrieNode()
        cnt1 = count_and_insert(nums, high+1)
        root = TrieNode()
        cnt2 = count_and_insert(nums, 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):
                num_bit = (num >> i) & 1
                if node.children[num_bit] is None:
                    node.children[num_bit] = TrieNode()
                node = node.children[num_bit]
                node.visited += 1

        def count_and_insert(nums, limit):
            cnt = 0
            for num in nums:
                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 == 1:
                        if node.children[num_bit]:
                            cnt += node.children[num_bit].visited
                        node = node.children[1 - num_bit]
                    else:
                        node = node.children[num_bit]
                insert(num)
            return cnt
        
        root = TrieNode()
        cnt1 = count_and_insert(nums, high+1)
        root = TrieNode()
        cnt2 = count_and_insert(nums, 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:
        cnt = 0

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

        def count_and_insert(nums, limit):
            # count nums[i] ^ nums[j] < limit
            cnt = 0
            for num in nums:
                node = root
                for i in range(15, -1, -1):
                    if not node:
                        break
                    limit_bit = (limit >> i) & 1
                    num_bit = (num >> i) & 1
                    if limit_bit == 1:
                        if node.children[num_bit]:
                            cnt += node.children[num_bit].visited
                        node = node.children[1 - num_bit]
                    else:
                        node = node.children[num_bit]
                insert(num)
            return cnt

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