Count Triplets with Even XOR Set Bits I

Count Triplets with Even XOR Set Bits I

What is this problem about?

The Count Triplets with Even XOR Set Bits I interview question involves three arrays a, b, and c. You need to count the number of triplets $(i, j, k)$ such that the XOR sum of the elements at those indices, $a[i] \oplus b[j] \oplus c[k]$, has an even number of set bits (1s) in its binary representation.

Why is this asked in interviews?

Amazon uses this to test basic bit manipulation interview pattern skills and logical simplification. The property of the "parity of set bits" is distributive over XOR. Specifically, $Parity(x \oplus y) = Parity(x) \oplus Parity(y)$. This means you don't need to actually calculate the XOR sum for every triplet; you only need to know the parity of set bits for each individual number.

Algorithmic pattern used

The problem uses Parity Counting.

1. For each array, count how many numbers have an "even" parity of set bits and how many have an "odd" parity.
   • Let $E_a, O_a$ be the counts for array a, and so on.
2. A triplet's XOR sum has even parity if the XOR of their individual parities is 0.
3. Possible parity combinations for even result (0):
   • (Even, Even, Even): $E_a imes E_b imes E_c$
   • (Even, Odd, Odd): $E_a imes O_b imes O_c$
   • (Odd, Even, Odd): $O_a imes E_b imes O_c$
   • (Odd, Odd, Even): $O_a imes O_b imes E_c$
4. Sum these four products.

Example explanation

a=[1], b=[2], c=[3] (Binaries: 1 is 01 (O), 2 is 10 (O), 3 is 11 (E))

• Array a: $E=0, O=1$
• Array b: $E=0, O=1$
• Array c: $E=1, O=0$ Triplets:
• (O, O, E): $1 imes 1 imes 1 = 1$.
• Total = 1. Check: $1 \oplus 2 \oplus 3 = 01 \oplus 10 \oplus 11 = 00$. Set bits = 0 (Even). Correct!

Common mistakes candidates make

• Brute Force: Checking every combination of $i, j, k$ ($O(N^3)$), which is unnecessary.
• Set Bit Calculation: Calculating the bit count inside the triple loop instead of precalculating the parities for each element.
• Misunderstanding XOR Parity: Thinking that the number of set bits in $X \oplus Y$ is the sum of set bits in $X$ and $Y$ (it's actually $count(X) + count(Y) - 2 imes count(X \cap Y)$). However, the parity property $P(X \oplus Y) = P(X) \oplus P(Y)$ always holds.

Interview preparation tip

Whenever a problem asks about the "parity of set bits" after an XOR operation, remember that XOR behaves like addition modulo 2 for each bit position. This makes the parity property a very powerful shortcut.