Taro Logo

Count Pairs With XOR in a Range

Hard
Google logo
Google
Topics:
ArraysBit Manipulation

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.

For example:

nums = [1, 4, 2, 7], low = 2, high = 6 The nice pairs are:

  • (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

So, the output is 6.

Another example:

nums = [9, 8, 4, 2, 1], low = 5, high = 14 The nice pairs are:

  • (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

So, the output is 8.

Constraints:

  • 1 <= nums.length <= 2 * 10^4
  • 1 <= nums[i] <= 2 * 10^4
  • 1 <= low <= high <= 2 * 10^4

How would you efficiently find the number of nice pairs in the given array?

Solution


Brute Force Solution

The most straightforward approach is to iterate through all possible pairs (i, j) where 0 <= i < j < nums.length, calculate nums[i] XOR nums[j], and check if the result falls within the range [low, high]. If it does, increment a counter.

def count_nice_pairs_brute_force(nums, low, high):
    count = 0
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            xor_val = nums[i] ^ nums[j]
            if low <= xor_val <= high:
                count += 1
    return count

Time Complexity: O(n^2), where n is the length of the nums array, due to the nested loops. Space Complexity: O(1), as we only use a constant amount of extra space.

Optimal Solution

An optimized approach involves using a hash map (or dictionary) to store the frequency of each number in the nums array. We can iterate through the array once, and for each number nums[i], check how many numbers nums[j] exist such that low <= (nums[i] XOR nums[j]) <= high.

To do this, we iterate through the numbers and consider nums[i] ^ low <= nums[j] <= nums[i] ^ high. The frequency of each number encountered can then be used to obtain the total number of 'nice pairs'.

def count_nice_pairs_optimal(nums, low, high):
    count = 0
    freq = {}
    for num in nums:
        lower_bound = num ^ high
        upper_bound = num ^ low
        
        lower_count = 0
        upper_count = 0
        
        for k, v in freq.items():
            if (num ^ k) >= low and (num ^ k) <= high:
                count += v
                
        freq[num] = freq.get(num, 0) + 1
    return count


def count_nice_pairs_optimal_v2(nums, low, high):
    count = 0
    freq = {}
    for i in range(len(nums)):
        for j in range(i):
            xor_val = nums[i] ^ nums[j]
            if low <= xor_val <= high:
                count +=1
        
        freq[nums[i]] = freq.get(nums[i], 0) + 1
    return count

Time Complexity: O(n), where n is the length of nums. On average the frequency map provides O(1) lookup. Space Complexity: O(n) in the worst case, where n is the length of nums, since the hash map might store all unique elements of nums.

Edge Cases

  • Empty array: If nums is empty, there are no pairs, so the result is 0.
  • Single element array: If nums contains only one element, there are no pairs, so the result is 0.
  • low > high: If low is greater than high, the range is invalid, and there can be no nice pairs. The problem states that 1 <= low <= high <= 2 * 10^4, so we do not have to account for this edge case.
  • Duplicate numbers: The algorithm should correctly handle duplicate numbers in the input array. The frequency map helps in counting the pairs accurately even with duplicates.