Count Triplets with Even XOR Set Bits I - Video Solutions

Problem Overview: You are given three arrays and need to count triplets (a, b, c) where one element is chosen from each array. A triplet is valid if the XOR value a ^ b ^ c contains an even number of set bits. The key challenge is recognizing that only the parity of the set bit count matters.

Approach 1: Brute Force Triplets (O(n * m * k) time, O(1) space)

Check every possible triplet by iterating through the three arrays using three nested loops. For each combination, compute x = a ^ b ^ c and count its set bits using a popcount operation. If the number of set bits is even, increment the answer. This approach is straightforward and helps verify correctness, but it becomes slow when arrays grow because the complexity multiplies across all three lengths.

Approach 2: Bit Parity Counting (O(n + m + k) time, O(1) space)

The optimal observation: the parity of set bits in an XOR equals the XOR of the individual parities. In other words, parity(popcount(a ^ b ^ c)) = pa ^ pb ^ pc, where pa, pb, and pc represent whether each number has an odd (1) or even (0) number of set bits. The result is even when this XOR equals 0.

First compute the set-bit parity of every number in each array. Count how many values have even parity and how many have odd parity. Then combine counts instead of enumerating triplets. Valid triplets occur when the XOR of the three parities equals 0, which happens for combinations like (even, even, even) or any case where exactly two are odd. Multiply the corresponding counts to get the total. This converts a triple nested iteration into simple counting.

This problem relies heavily on understanding XOR properties and bit-count parity. If XOR and popcount operations feel unfamiliar, reviewing bit manipulation fundamentals and parity tricks will make these patterns much easier to spot. Similar counting optimizations also appear in problems involving arrays and XOR-based constraints.

Recommended for interviews: Start by explaining the brute force enumeration to show the direct interpretation of the problem. Then introduce the parity insight that collapses the search space. Interviewers typically expect the parity-counting approach because it demonstrates strong understanding of XOR properties and efficient counting techniques.