{x}
blog image

Count Pairs With XOR in a Range

Given a (0-indexed) integer array nums and two integers low and high, return the number of nice pairs.

A nice pair is a pair (i, j) where 0 <= i < j < nums.length and low <= (nums[i] XOR nums[j]) <= high.

 

Example 1:

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

Example 2:

Input: nums = [9,8,4,2,1], low = 5, high = 14
Output: 8
Explanation: All nice pairs (i, j) are as follows:
​​​​​    - (0, 2): nums[0] XOR nums[2] = 13
    - (0, 3): nums[0] XOR nums[3] = 11
    - (0, 4): nums[0] XOR nums[4] = 8
    - (1, 2): nums[1] XOR nums[2] = 12
    - (1, 3): nums[1] XOR nums[3] = 10
    - (1, 4): nums[1] XOR nums[4] = 9
    - (2, 3): nums[2] XOR nums[3] = 6
    - (2, 4): nums[2] XOR nums[4] = 5

 

Constraints:

  • 1 <= nums.length <= 2 * 104
  • 1 <= nums[i] <= 2 * 104
  • 1 <= low <= high <= 2 * 104

Solution Explanation: Count Pairs With XOR in a Range

This problem asks to find the number of pairs (i, j) in an array nums where low <= nums[i] XOR nums[j] <= high. A brute-force approach would have O(n^2) time complexity, which is inefficient for large arrays. The optimal solution utilizes a Trie data structure to achieve a significantly improved time complexity.

Approach: Using a 0-1 Trie

A 0-1 Trie (binary Trie) is a tree-like data structure where each node represents a bit. The path from the root to a leaf node represents a unique number. This structure is particularly efficient for bitwise operations like XOR.

The solution involves these steps:

  1. Trie Node: Define a Trie node with children (to store left and right children representing 0 and 1 bits respectively) and cnt (to count the number of numbers ending at this node).

  2. insert(x) Function: This function inserts a number x into the Trie. It traverses the bits of x from most significant to least significant, creating nodes as needed and incrementing the cnt of each visited node.

  3. search(x, limit) Function: This function counts the numbers in the Trie whose XOR with x is less than limit. It iterates through the bits of x and limit. If a bit in limit is 1, it adds the count of the subtree corresponding to the same bit in x and then explores the subtree corresponding to the opposite bit (to cover all possibilities for the remaining bits). If a bit in limit is 0, it continues searching only within the subtree matching that bit in x.

  4. Main Algorithm:

    • Initialize an empty Trie.
    • Iterate through nums:
      • For each number x, call search(x, high + 1) to get the count of numbers with XOR less than high + 1.
      • Similarly, call search(x, low) to get the count of numbers with XOR less than low.
      • The difference between these two counts represents the number of pairs satisfying low <= XOR <= high for the current x. Add this difference to the total count ans.
      • Insert x into the Trie.
    • Return the final count ans.

Time and Space Complexity Analysis

  • Time Complexity: The insert and search operations in the Trie take O(log M) time, where M is the maximum value in nums. Since we iterate through nums once, and each iteration performs two search operations and one insert operation, the overall time complexity is O(n log M). For this problem, the maximum value of nums is 2 * 10^4, thus log M is approximately 16 which can be considered constant. Therefore the time complexity is dominated by O(n).

  • Space Complexity: The space used by the Trie is proportional to the number of nodes, which is at most O(n log M). This is because each number in nums can potentially create a path of length log M in the Trie.

Code Examples

The code examples in Python, Java, C++, and Go are provided in the original response. They all follow the algorithm described above, implementing the Trie structure and its associated functions to efficiently count the pairs. The core logic remains consistent across all languages.