Problem Description

You are given three integer arrays a, b, and c. Your task is to count how many triplets (a[i], b[j], c[k]) exist such that when you compute the bitwise XOR of these three elements (a[i] XOR b[j] XOR c[k]), the result has an even number of set bits (1s in its binary representation).

For example, if we have:

• a[i] = 5 (binary: 101, has 2 set bits)
• b[j] = 3 (binary: 011, has 2 set bits)
• c[k] = 6 (binary: 110, has 2 set bits)
• Their XOR: 5 XOR 3 XOR 6 = 0 (binary: 000, has 0 set bits)
• Since 0 is even, this triplet would be counted.

The key insight is that when XORing numbers, the parity (odd/even nature) of set bits in the result depends on the sum of parities of set bits in the individual numbers. If the total count of set bits across all three numbers has a specific parity pattern, the XOR result will have an even number of set bits.

The solution leverages this property by:

1. Counting how many numbers in each array have an odd vs even number of set bits
2. Finding all combinations where the XOR would result in an even number of set bits
3. Using the formula that checks if (i + j + k) is even, where i, j, k represent the parity (0 for even, 1 for odd) of set bits in numbers from arrays a, b, c respectively

Intuition

When we XOR multiple numbers together, there's a beautiful mathematical property about the parity of set bits. Let's think about what happens when we XOR two bits:

• 0 XOR 0 = 0
• 0 XOR 1 = 1
• 1 XOR 0 = 1
• 1 XOR 1 = 0

Notice that XOR essentially counts whether we have an odd or even number of 1s at each bit position. If we have an even number of 1s, the result is 0; if odd, the result is 1.

This extends to the entire number: when we XOR three numbers a[i] XOR b[j] XOR c[k], the parity of set bits in the result depends on how the set bits in the original numbers combine.

Here's the key insight: instead of computing the actual XOR for every possible triplet (which would be expensive), we can work with just the parity of set bits. If a number has an odd number of set bits, we can represent it as 1, and if it has an even number, we represent it as 0.

When XORing three numbers, the result will have an even number of set bits if and only if the sum of the parities of the three numbers is even. Why? Because:

• If all three have even parity (0+0+0=0): even result
• If two have odd parity and one even (1+1+0=2): even result
• If all three have odd parity (1+1+1=3): odd result
• If one has odd parity and two even (1+0+0=1): odd result

So we want cases where (parity_a + parity_b + parity_c) is even, which means (parity_a + parity_b + parity_c) % 2 == 0.

This transforms our problem from checking every triplet's XOR (O(n³) operations) to simply counting parities and multiplying counts (O(n) operations). We count how many numbers in each array have odd/even parity of set bits, then multiply the counts for valid parity combinations.

Solution Approach

Based on our intuition about parity, we can implement an efficient solution using counting and bit manipulation.

Step 1: Count Parities

First, we create three counters (cnt1, cnt2, cnt3) to track the parity of set bits for each number in the arrays:

• For each number x in array a, we compute x.bit_count() & 1
  • bit_count() gives us the number of 1s in the binary representation
  • & 1 gives us the parity (0 if even, 1 if odd)
• We do the same for arrays b and c

This gives us:

• cnt1[0] = count of numbers in a with even number of set bits
• cnt1[1] = count of numbers in a with odd number of set bits
• Similarly for cnt2 and cnt3

Step 2: Enumerate Valid Combinations

We iterate through all possible parity combinations using three nested loops:

for i in range(2):      # parity from array a (0 or 1)
    for j in range(2):  # parity from array b (0 or 1)
        for k in range(2):  # parity from array c (0 or 1)

Step 3: Check Valid Parity

For each combination (i, j, k), we check if the XOR result would have an even number of set bits:

• The condition (i + j + k) & 1 ^ 1 checks if the sum is even
  • (i + j + k) & 1 gives us the parity of the sum (0 if even, 1 if odd)
  • ^ 1 flips the bit (XOR with 1), so we get 1 if the sum is even, 0 if odd
• When this condition is true, the XOR of any triplet with these parities will have an even number of set bits

Step 4: Count Valid Triplets

When we find a valid parity combination, we multiply the counts:

ans += cnt1[i] * cnt2[j] * cnt3[k]

This gives us the total number of triplets (a[x], b[y], c[z]) where:

• a[x] has parity i
• b[y] has parity j
• c[z] has parity k

The valid combinations are:

• (0, 0, 0): all even parities → sum = 0 (even)
• (0, 1, 1): one even, two odd → sum = 2 (even)
• (1, 0, 1): two odd, one even → sum = 2 (even)
• (1, 1, 0): two odd, one even → sum = 2 (even)

Time Complexity: O(n + m + p) where n, m, p are the lengths of arrays a, b, c respectively. Space Complexity: O(1) as we only use fixed-size counters.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given arrays:

• a = [5, 2]
• b = [3, 8]
• c = [6, 1]

Step 1: Analyze each number's set bits and parity

For array a:

• 5 = binary 101 → 2 set bits → even parity (represented as 0)
• 2 = binary 010 → 1 set bit → odd parity (represented as 1)

For array b:

• 3 = binary 011 → 2 set bits → even parity (0)
• 8 = binary 1000 → 1 set bit → odd parity (1)

For array c:

• 6 = binary 110 → 2 set bits → even parity (0)
• 1 = binary 001 → 1 set bit → odd parity (1)

Step 2: Count parities for each array

• cnt1[0] = 1 (one number with even parity: 5)
• cnt1[1] = 1 (one number with odd parity: 2)
• cnt2[0] = 1 (one number with even parity: 3)
• cnt2[1] = 1 (one number with odd parity: 8)
• cnt3[0] = 1 (one number with even parity: 6)
• cnt3[1] = 1 (one number with odd parity: 1)

Step 3: Find valid parity combinations

We need combinations where (i + j + k) is even:

Step 4: Calculate total

Total valid triplets = 1 + 1 + 1 + 1 = 4

Step 5: Verify with actual triplets

Let's verify by checking all 8 possible triplets:

1. (5, 3, 6): 5 XOR 3 XOR 6 = 0 → binary 000 → 0 set bits (even) ✓
2. (5, 3, 1): 5 XOR 3 XOR 1 = 7 → binary 111 → 3 set bits (odd) ✗
3. (5, 8, 6): 5 XOR 8 XOR 6 = 15 → binary 1111 → 4 set bits (even) ✓
4. (5, 8, 1): 5 XOR 8 XOR 1 = 12 → binary 1100 → 2 set bits (even) ✓
5. (2, 3, 6): 2 XOR 3 XOR 6 = 7 → binary 111 → 3 set bits (odd) ✗
6. (2, 3, 1): 2 XOR 3 XOR 1 = 0 → binary 000 → 0 set bits (even) ✓
7. (2, 8, 6): 2 XOR 8 XOR 6 = 12 → binary 1100 → 2 set bits (even) ✓
8. (2, 8, 1): 2 XOR 8 XOR 1 = 11 → binary 1011 → 3 set bits (odd) ✗

Valid triplets: #1, #3, #4, #6 = 4 triplets ✓

The counting approach correctly identified 4 valid triplets without computing any XOR operations, demonstrating how we can solve this problem efficiently using parity counting.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of arrays a, b, and c. This is because:

• Creating cnt1 requires iterating through array a to compute x.bit_count() & 1 for each element, which takes O(n) time
• Creating cnt2 requires iterating through array b, which takes O(n) time
• Creating cnt3 requires iterating through array c, which takes O(n) time
• The triple nested loop iterates exactly 2×2×2 = 8 times (constant), and each iteration performs constant-time operations (dictionary lookups and multiplication)
• Overall: O(n) + O(n) + O(n) + O(1) = O(n)

The space complexity is O(1). This is because:

• Each Counter (cnt1, cnt2, cnt3) stores at most 2 key-value pairs (keys can only be 0 or 1, since x.bit_count() & 1 returns either 0 or 1)
• The space used by the Counters is constant regardless of input size
• The variable ans and loop variables i, j, k use constant space
• Overall: O(1)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding XOR Parity Property

Pitfall: Assuming that XOR of three numbers with even bit counts always results in an even bit count.

Example:

• a = 3 (binary: 011, 2 set bits - even)
• b = 5 (binary: 101, 2 set bits - even)
• c = 6 (binary: 110, 2 set bits - even)
• 3 XOR 5 XOR 6 = 0 (binary: 000, 0 set bits - even) ✓

But consider:

• a = 3 (binary: 011, 2 set bits - even)
• b = 3 (binary: 011, 2 set bits - even)
• c = 0 (binary: 000, 0 set bits - even)
• 3 XOR 3 XOR 0 = 0 (binary: 000, 0 set bits - even) ✓

The rule isn't about individual parities but their sum modulo 2.

2. Integer Overflow in Large Arrays

Pitfall: When arrays are large, the multiplication cnt1[i] * cnt2[j] * cnt3[k] might overflow in languages with fixed integer sizes.

Solution: In Python this isn't an issue due to arbitrary precision integers, but in other languages:

# Use long/int64 or modular arithmetic if needed
result = (result + (cnt1[i] * cnt2[j] % MOD * cnt3[k]) % MOD) % MOD

3. Incorrect Parity Check Logic

Pitfall: Writing the condition as (i + j + k) & 1 ^ 1 which evaluates as ((i + j + k) & 1) ^ 1 due to operator precedence, when you might intend (i + j + k) & (1 ^ 1).

Solution: Be explicit with the condition:

# Clear and readable
if (parity_a + parity_b + parity_c) % 2 == 0:
    # Process valid combination

# Or using bitwise operations
if ((parity_a + parity_b + parity_c) & 1) == 0:
    # Process valid combination

4. Missing Edge Cases

Pitfall: Not handling arrays with all zeros or single elements properly.

Example Issue:

# Arrays with zeros
a = [0, 0, 0]  # All have 0 set bits (even)
b = [1]        # Has 1 set bit (odd)
c = [1]        # Has 1 set bit (odd)
# 0 XOR 1 XOR 1 = 0 (0 set bits - even)
# Should count 3 triplets

Solution: The current approach handles this correctly since 0.bit_count() = 0 (even parity), but always verify with test cases.

5. Using Wrong Bit Counting Method

Pitfall: In older Python versions or other languages, bit_count() might not be available.

Solution: Implement a helper function:

def count_bits(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

# Or use bin() function
def count_bits_alt(n):
    return bin(n).count('1')

# Then use in main logic
parity_count_a = Counter(count_bits(x) & 1 for x in a)

6. Confusion About Valid Parity Combinations

Pitfall: Forgetting why only certain parity combinations work.

Clarification: The XOR result has even set bits when:

• All three numbers have even parity (0+0+0=0, even)
• One has even parity, two have odd parity (0+1+1=2, even)

Invalid combinations:

• All three have odd parity (1+1+1=3, odd)
• Two have even, one has odd (0+0+1=1, odd)