<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:
        num_bits = 15  # Number of bits for prefix calculation
        prefix_count = [0] * (1 << (num_bits + 1))  # Array to store count of each prefix
        result = 0  # Variable to store the result
        high += 1  # Adjust high to be exclusive

        # Iterate through each number in the nums list
        for num in nums:
            # Iterate through each bit position from most significant to least significant
            for bit_position in range(num_bits, -1, -1):
                # Calculate the upper and lower bounds for the current bit position
                upper_bound = high >> bit_position
                lower_bound = low >> bit_position

                # If the current bit of high is 1, add the count of prefixes that would result in the current prefix
                if upper_bound % 2 == 1:
                    result += prefix_count[(1 << num_bits - bit_position) + (upper_bound ^ 1 ^ (num >> bit_position))]

                # If the current bit of low is 1, subtract the count of prefixes that would result in the current prefix
                if lower_bound % 2 == 1:
                    result -= prefix_count[(1 << num_bits - bit_position) + (lower_bound ^ 1 ^ (num >> bit_position))]

            # Update the prefix count for the current number
            for bit_position in range(num_bits, -1, -1):
                prefix_count[(num >> bit_position) + (1 << (num_bits - bit_position))] += 1

        return result        
19700