Count Triplets with Even XOR Set Bits II - Video Solutions

Problem Overview: Given an array of integers, count triplets (i, j, k) such that the XOR of the three numbers contains an even number of set bits. The challenge is recognizing how XOR interacts with bit counts and reducing the brute-force triplet search.

Approach 1: Brute Force Triplet Enumeration (O(n³) time, O(1) space)

Check every triplet (i, j, k) with three nested loops. For each combination compute x = nums[i] ^ nums[j] ^ nums[k] and count its set bits using popcount. If the number of set bits is even, increment the answer. This approach is straightforward and useful for validating logic on small inputs, but it becomes impractical for large arrays because the number of triplets grows as n^3. The method mainly demonstrates the direct application of Bit Manipulation operations.

Approach 2: Parity Observation with Counting (O(n) time, O(1) space)

The key observation: the parity of the number of set bits in a ^ b ^ c depends only on the parity of set bits in each number. Let p(x) = popcount(x) % 2. Then popcount(a ^ b ^ c) % 2 = p(a) ^ p(b) ^ p(c). For the XOR to contain an even number of set bits, this value must equal 0. That means either all three numbers have even bit parity, or exactly two numbers have odd parity and one has even parity.

Scan the array once and compute p(x) for each element using a popcount operation from bit manipulation. Maintain counts evenCount and oddCount. Valid triplets come from two patterns:

C(evenCount, 3) → all numbers have even bit parity.

C(oddCount, 2) * evenCount → two odd-parity numbers and one even-parity number.

This reduces the entire computation to simple combinatorics after a single pass through the array. Only two counters are stored, so the space complexity stays constant. The idea combines parity analysis with counting patterns often used in Array problems.

Recommended for interviews: Interviewers expect the parity-based counting approach. The brute force solution shows understanding of XOR and set bit counting, but the optimized solution demonstrates the real insight: only the parity of popcount matters. Once you convert numbers into parity buckets, the triplet counting becomes a small combinatorics problem with linear time complexity.