XOR Parity Pairs
In large-scale data processing and network protocols, ensuring data integrity often involves checksums and parity checks. One common operation is the bitwise XOR, which can reveal differences or combine data streams. This problem challenges you to efficiently identify pairs of data points whose combined bitwise XOR operation results in a specific parity characteristic, a pattern that can be crucial for anomaly detection or cryptographic applications.
Given an array of non-negative integers nums, your task is to find the total number of unique pairs (i, j) such that i < j, and the bitwise XOR sum nums[i] ^ nums[j] has an even number of set bits (1s).
nums: An array of non-negative integers.nums will not be empty.nums contains only one element, no pairs (i, j) with i < j can be formed, so the result should be 0.nums can be large, up to 2^31 - 1, requiring standard integer types (e.g., number in JavaScript/TypeScript, int in Java/C++).__builtin_popcount in C++, or an iterative approach).Examples
Example 1
Input:
nums = [1, 2, 3]
Output:
1
Note:
Numbers and their set bit parities:
Pairs (i, j) with i < j:
Example 2
Input:
nums = [4, 7, 10, 13]
Output:
3
Note:
Numbers and their set bit parities:
Recalculating:
count_even = 1 (for 10)
count_odd = 3 (for 4, 7, 13)
Pairs from even parity numbers: 1 * (1 - 1) / 2 = 0
Pairs from odd parity numbers: 3 * (3 - 1) / 2 = 3
Total = 3. Still 3, just different numbers contributing. The explanation needs to be correct.
Let's update the explanation for 7 and 13 to reflect odd parity:
Numbers with odd set bit parity: [4, 7, 13] Numbers with even set bit parity: [10]
Only pairs formed by numbers of the same set bit parity count. Pairs from odd parity numbers: (4,7), (4,13), (7,13) -> 3 pairs. Pairs from even parity numbers: None (only one number). Total valid pairs: 3.
Example 3
Input:
nums = [5, 5, 5]
Output:
3
Note:
All numbers are 5 (101), which has 2 set bits (even parity). Since all numbers have even set bit parity, all pairs will result in an even number of set bits after XOR. There are 3 elements, so the number of unique pairs is 3 * (3 - 1) / 2 = 3.
Constraints
1 <= nums.length <= 10^50 <= nums[i] < 2^31O(N) or O(N log MAX_VAL) where MAX_VAL is the maximum possible value of nums[i]. An O(N^2) solution will likely exceed typical time limits.O(1) or O(N) if auxiliary storage for counts is used.Loading editor...