💬 Discord
Sign In
NeetCode #851LC-3199EasyBit Manipulation
← Back to All Problems

#851 · #3199 · Count Triplets with Even XOR Set Bits I(统计异或置位数均为偶数的三元组 I)

📌 Problem Statement & Constraints

Given three integer arrays a, b and c, count the triplets (a[i], b[j], c[k]) whose bitwise XOR has an even number of set bits. Constraints: 1 <= a.length, b.length, c.length <= 100, 0 <= a[i], b[i], c[k] <= 100.

💡 Core Algorithmic Approaches

  1. Only the parity of each element's set-bit count matters, since the parity of a XOR is the XOR of the parities.
  2. Count, in each array, how many elements have an even popcount and how many have an odd popcount.
  3. A triplet is valid when the three parities sum to an even number: all even, or exactly two odd.
  4. Multiply the corresponding counts for the four valid parity combinations and sum them.

💻 Benchmark Python3 Implementation

class Solution:
    def tripletCount(self, a: List[int], b: List[int], c: List[int]) -> int:
        def parity_counts(arr):
            cnt = [0, 0]                # indexed by popcount parity
            for x in arr:
                cnt[bin(x).count("1") & 1] += 1
            return cnt

        ca, cb, cc = parity_counts(a), parity_counts(b), parity_counts(c)
        ans = 0
        for i in range(2):
            for j in range(2):
                for k in range(2):
                    if (i + j + k) % 2 == 0:   # the XOR has an even popcount
                        ans += ca[i] * cb[j] * cc[k]
        return ans

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n + m + p): one pass per array plus a constant 8-combination loop.
💾 Space Complexity
O(1): six counters.

⚠️ Interview Pitfalls & Follow-ups

  • Enumerating all triplets: up to 10^6 combinations is fine at these constraints but misses the parity insight the problem teaches.
  • Checking the XOR value rather than its parity: the parity of a XOR is the XOR of the parities, so the actual values are irrelevant.
  • Keeping only the odd counts: the all-even combination is also valid, so both parities must be tracked.
  • Mixing up which combinations are valid: exactly 0 or 2 of the three parities must be odd, never 1 or 3.