<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>
from collections import defaultdict
class Group:
	def __init__(self, most_significant_bit: int):
		self.most_significant_bit = most_significant_bit
		self.sized_prefixes_freq = [defaultdict(lambda: 0) for _ in range(most_significant_bit)]
		self.total_nums = 0
	def add_num(self, num: int):
		self.total_nums += 1
		for bit in range(self.most_significant_bit):
			zeroed_bits = self.most_significant_bit - 1 - bit
			prefix = (num >> zeroed_bits) << zeroed_bits
			self.sized_prefixes_freq[bit][prefix] += 1
	def solve(self, k: int):
		removed_pairs = 0
		k_mask = 0
		for bit in range(self.most_significant_bit):
			bit_index = self.most_significant_bit - 1 - bit
			k_bit = k & (1 << bit_index)
			
			if k_bit == 0:
				bad_mask = k_mask | (1 << bit_index)
				
				for prefix in self.sized_prefixes_freq[bit]:
					removed_pairs += self.sized_prefixes_freq[bit].get(prefix, 0) * self.sized_prefixes_freq[bit].get(prefix ^ bad_mask, 0)
			else:
				k_mask |= (1 << bit_index)
		return self.total_nums * (self.total_nums - 1) // 2 - removed_pairs // 2
class Solver:
	def __init__(self, nums: List[int], k: int):
		self.nums = nums
		self.k = k
	def special_solve_zero_k(self):
		freq = defaultdict(lambda: 0)
		for num in self.nums:
			freq[num] += 1
		pairs = 0
		for num, count in freq.items():
			pairs += count * (count - 1) // 2
		return pairs
	def solve(self):
		if self.k == 0:
			return self.special_solve_zero_k()

		most_significant_bit = 0
		temp_k = self.k
		while temp_k > 0:
			most_significant_bit += 1
			temp_k >>= 1

		prefix_groups = defaultdict(lambda: Group(most_significant_bit))
		prefix_mask = (1 << most_significant_bit) - 1
		for num in self.nums:
			num_prefix = (num >> most_significant_bit) << most_significant_bit
			num_suffix = num & prefix_mask
			prefix_groups[num_prefix].add_num(num_suffix)
		
		pairs = 0
		for prefix, prefix_group in prefix_groups.items():
			pairs += prefix_group.solve(self.k)
		return pairs

class Solution:
	def countPairs(self, nums: List[int], low: int, high: int):
		low_solver = Solver(nums, low - 1)
		high_solver = Solver(nums, high)
		return high_solver.solve() - low_solver.solve()
21000