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 * 1041 <= nums[i] <= 2 * 1041 <= low <= high <= 2 * 104This approach involves checking every possible pair (i, j) strictly where i < j, calculating their XOR, and checking if the result lies within the given range [low, high].
This C solution iterates through each combination of pairs, computes the XOR, and checks if it lies within the range [low, high]. If it does, it increments the count. Finally, it returns the count of such nice pairs.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), where n is the number of elements in the array, since we iterate over all possible pairs. Space Complexity: O(1), as we are not using any extra space proportional to the input size.
This approach involves building a Trie where each path represents a binary number in the array. Using the properties of XOR, we can efficiently count nice pairs by traversing this Trie.
This C solution uses a Trie to efficiently count the number of pairs whose XOR falls within a given range. By storing each number in binary form, it reduces search complexity when checking potential XOR values against the limits. The method achieves this by using Trie nodes to traverse potential number paths.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * 15), where 15 is the number of bits required to represent numbers up to 20000. Space Complexity: O(n * 15).
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), where n is the number of elements in the array, since we iterate over all possible pairs. Space Complexity: O(1), as we are not using any extra space proportional to the input size. |
| Optimized Bit-Operation Approach Using Trie | Time Complexity: O(n * 15), where 15 is the number of bits required to represent numbers up to 20000. Space Complexity: O(n * 15). |
Count the Number of Fair Pairs - Leetcode 2563 - Python • NeetCodeIO • 15,313 views views
Watch 9 more video solutions →Practice Count Pairs With XOR in a Range with our built-in code editor and test cases.
Practice on FleetCode