LeetCode Solutions Blog

Count Pairs With XOR in a Range

Difficulty: Hard

Problem Description

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.

Key Insights

XOR operation properties can be leveraged to efficiently compute pairs that fall within the specified range.
A brute-force solution would involve checking all pairs, leading to O(n^2) time complexity.
Utilizing a Trie data structure can optimize the search for valid pairs by allowing efficient calculation of XOR values.

Space and Time Complexity

Time Complexity: O(n log(max_value)), where max_value is the maximum possible value of the elements in nums due to the depth of the Trie. Space Complexity: O(n), for storing elements in the Trie.

Solution

The solution involves using a Trie to store binary representations of the numbers. For each number, we compute how many previously inserted numbers can form a nice pair with it by checking the range defined by low and high using XOR. The Trie helps to quickly find the number of valid pairs for each number processed.

Code Solutions

class TrieNode:
    def __init__(self):
        self.children = {}
        self.count = 0

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, num):
        node = self.root
        for i in range(16, -1, -1):  # 17 bits for numbers up to 2 * 10^4
            bit = (num >> i) & 1
            if bit not in node.children:
                node.children[bit] = TrieNode()
            node = node.children[bit]
            node.count += 1

    def countPairsInRange(self, num, low, high):
        node = self.root
        count = 0
        for i in range(16, -1, -1):
            if node is None:
                break
            
            bit = (num >> i) & 1
            low_bit = (low >> i) & 1
            high_bit = (high >> i) & 1
            
            if low_bit == 1:
                # If the bit of low is 1, we can only go right
                if bit in node.children:
                    node = node.children[bit]
                else:
                    break
            else:
                # If the bit of low is 0, we can go left and right
                if bit in node.children:
                    count += node.children[bit].count
                if high_bit == 1:
                    if 1 - bit in node.children:
                        node = node.children[1 - bit]
                    else:
                        break
                else:
                    if bit in node.children:
                        node = node.children[bit]
                    else:
                        break
        
        return count

def countNicePairs(nums, low, high):
    trie = Trie()
    result = 0
    for num in nums:
        result += trie.countPairsInRange(num, low, high)
        trie.insert(num)
    return result

# Example usage
print(countNicePairs([1, 4, 2, 7], 2, 6))  # Output: 6