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:
So, the output is 6.
Another example:
nums = [9, 8, 4, 2, 1], low = 5, high = 14 The nice pairs are:
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?
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.
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
.
nums
is empty, there are no pairs, so the result is 0.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.