Frontend School

XOR Parity Pairs

DSA
medium

XOR Parity Pairs

Medium
Bit Manipulation
Arrays

Overview

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.

What you need to do / Task

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).

Input & output

  • Input: nums: An array of non-negative integers.
  • Output: An integer representing the total count of such pairs.

Clarifications

  • The input array nums will not be empty.
  • If nums contains only one element, no pairs (i, j) with i < j can be formed, so the result should be 0.
  • The numbers in nums can be large, up to 2^31 - 1, requiring standard integer types (e.g., number in JavaScript/TypeScript, int in Java/C++).
  • You may use any standard method to count set bits (e.g., __builtin_popcount in C++, or an iterative approach).

Examples

1

Example 1

Input:

nums = [1, 2, 3]

Output:

1

Note:

Numbers and their set bit parities:

  • 1 (001): 1 set bit (odd parity)
  • 2 (010): 1 set bit (odd parity)
  • 3 (011): 2 set bits (even parity)

Pairs (i, j) with i < j:

  • (1, 2): nums[0] ^ nums[1] = 1 ^ 2 = 3 (011). Has 2 set bits (even parity). Counts.
  • (1, 3): nums[0] ^ nums[2] = 1 ^ 3 = 2 (010). Has 1 set bit (odd parity). Does not count.
  • (2, 3): nums[1] ^ nums[2] = 2 ^ 3 = 1 (001). Has 1 set bit (odd parity). Does not count. Total valid pairs: 1.
2

Example 2

Input:

nums = [4, 7, 10, 13]

Output:

3

Note:

Numbers and their set bit parities:

  • 4 (0100): 1 set bit (odd parity)
  • 7 (0111): 3 set bits (odd parity) -> Correction: 3 set bits is odd. Oops, my internal check was wrong. Let's re-evaluate.
    • 4 (0100): popcount=1 (odd parity)
    • 7 (0111): popcount=3 (odd parity)
    • 10 (1010): popcount=2 (even parity)
    • 13 (1101): popcount=3 (odd parity)

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:

  • 4 (0100): 1 set bit (odd parity)
  • 7 (0111): 3 set bits (odd parity)
  • 10 (1010): 2 set bits (even parity)
  • 13 (1101): 3 set bits (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.

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

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] < 2^31
  • The solution should aim for optimal time complexity, ideally O(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.
  • Space complexity should be O(1) or O(N) if auxiliary storage for counts is used.

What interviewers evaluate

  • Correctness: The algorithm must accurately count all valid pairs, handling various input scenarios and edge cases.
  • Efficiency: The solution should demonstrate an understanding of optimal time and space complexities for large inputs.
  • Bit Manipulation Mastery: Effective application of bitwise operations and understanding of their properties.
  • Problem-Solving Approach: Ability to analyze the problem, identify key properties, and derive an optimized solution.

Loading editor...