LeetCode 3199 - Count Triplets with Even XOR Set Bits I

LeetCode Problem 3199

Difficulty: 🟢 Easy
Topics: Array, Bit Manipulation

Solution

Problem Understanding

The problem gives us three integer arrays, a, b, and c. We must count how many triplets (a[i], b[j], c[k]) produce a bitwise XOR result with an even number of set bits.

A set bit is a bit equal to 1 in the binary representation of a number. For example:

• 5 in binary is 101, which has 2 set bits
• 7 in binary is 111, which has 3 set bits

The XOR operation compares bits position by position:

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

For every possible combination of one element from each array, we compute:

$$a[i] \oplus b[j] \oplus c[k]$$

Then we count how many of those results contain an even number of set bits.

The arrays are small:

• Each array length is at most 100
• Each value is at most 100

This means a brute force solution is technically feasible because:

$$100 \times 100 \times 100 = 1,000,000$$

One million operations is acceptable in most programming languages. However, the problem can still be optimized significantly using an important bit manipulation observation.

There are several edge cases worth noticing:

• Arrays may contain duplicate values, and every index combination counts separately.
• The XOR result itself may be 0, which has 0 set bits, and 0 is considered even.
• Arrays can contain only one element.
• Some numbers may already contain an even number of set bits while others contain an odd number, and the parity interaction is what matters.

Approaches

Brute Force

The brute force approach checks every possible triplet.

For each element in a, we iterate through every element in b, and for each pair we iterate through every element in c. We compute:

$$x = a[i] \oplus b[j] \oplus c[k]$$

Then we count how many set bits exist in x. If the count is even, we increment the answer.

This approach is correct because it explicitly evaluates every valid triplet exactly once. Nothing is skipped, so the final count is guaranteed to be accurate.

However, the runtime is:

$$O(|a| \times |b| \times |c|)$$

In the worst case this becomes:

$$100^3 = 1,000,000$$

Although acceptable here, we can do better by using a parity property of XOR.

Key Insight

The important observation is that we do not need the exact number of set bits. We only care whether the number of set bits is even or odd.

A useful XOR property is:

• XOR of numbers preserves parity of set bits
• Even parity XOR Even parity = Even parity
• Even parity XOR Odd parity = Odd parity
• Odd parity XOR Odd parity = Even parity

In other words, the parity behaves exactly like XOR itself.

If we define:

• 0 for even number of set bits
• 1 for odd number of set bits

then:

$$parity(a \oplus b \oplus c) = parity(a) \oplus parity(b) \oplus parity(c)$$

We want the final parity to be even, meaning:

$$parity(a) \oplus parity(b) \oplus parity(c) = 0$$

Instead of checking every triplet individually, we only need to know:

• how many numbers in each array have even parity
• how many have odd parity

Then we count valid combinations mathematically.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m × k)	O(1)	Checks every triplet directly
Optimal	O(n + m + k)	O(1)	Counts parity frequencies and combines mathematically

Algorithm Walkthrough

Optimal Algorithm

1. Traverse array a and count:

• how many numbers have an even number of set bits
• how many numbers have an odd number of set bits

2. Repeat the same process for arrays b and c.
3. For each number, determine parity by counting set bits:

• if the count is even, increment the even counter
• otherwise increment the odd counter

4. A triplet produces an even parity XOR result when the number of odd parities among the three elements is even.
5. There are four valid parity combinations:

• even, even, even
• even, odd, odd
• odd, even, odd
• odd, odd, even

6. Compute the total number of valid triplets using multiplication:

• aEven * bEven * cEven
• aEven * bOdd * cOdd
• aOdd * bEven * cOdd
• aOdd * bOdd * cEven

7. Return the sum of these four quantities.

Why it works

The parity of the number of set bits behaves exactly like XOR. A final XOR result has an even number of set bits if and only if the XOR of the three parity values equals 0.

This happens precisely when the number of odd-parity elements in the triplet is even. With three elements, that means either:

• all three are even
• exactly two are odd

By counting how many numbers belong to each parity group, we can compute the number of valid triplets directly without enumerating all combinations.

Python Solution

from typing import List

class Solution:
    def tripletCount(self, a: List[int], b: List[int], c: List[int]) -> int:
        def count_parity(nums: List[int]) -> tuple[int, int]:
            even_count = 0
            odd_count = 0

            for num in nums:
                set_bits = num.bit_count()

                if set_bits % 2 == 0:
                    even_count += 1
                else:
                    odd_count += 1

            return even_count, odd_count

        a_even, a_odd = count_parity(a)
        b_even, b_odd = count_parity(b)
        c_even, c_odd = count_parity(c)

        return (
            a_even * b_even * c_even +
            a_even * b_odd * c_odd +
            a_odd * b_even * c_odd +
            a_odd * b_odd * c_even
        )

The implementation starts by defining a helper function called count_parity. This function scans an array and separates its numbers into two categories:

• numbers with an even number of set bits
• numbers with an odd number of set bits

Python provides the convenient bit_count() method, which directly returns the number of set bits in an integer.

After processing arrays a, b, and c, we obtain six counts:

• a_even, a_odd
• b_even, b_odd
• c_even, c_odd

The final answer is computed using the four valid parity combinations that produce an even XOR parity.

Because all operations are simple counting and arithmetic, the implementation is both fast and memory efficient.

Go Solution

func tripletCount(a []int, b []int, c []int) int {
	countParity := func(nums []int) (int, int) {
		evenCount := 0
		oddCount := 0

		for _, num := range nums {
			setBits := 0
			value := num

			for value > 0 {
				setBits += value & 1
				value >>= 1
			}

			if setBits%2 == 0 {
				evenCount++
			} else {
				oddCount++
			}
		}

		return evenCount, oddCount
	}

	aEven, aOdd := countParity(a)
	bEven, bOdd := countParity(b)
	cEven, cOdd := countParity(c)

	return (
		aEven*bEven*cEven +
			aEven*bOdd*cOdd +
			aOdd*bEven*cOdd +
			aOdd*bOdd*cEven
	)
}

The Go implementation follows the same logic as the Python version. Since Go does not have a built-in bit_count() method for plain integers in the same way Python does, we manually count set bits using repeated bit shifting.

The loop:

for value > 0 {
    setBits += value & 1
    value >>= 1
}

extracts the least significant bit and shifts the number right until all bits are processed.

Go slices naturally handle empty or non-empty collections, although the problem guarantees each array contains at least one element.

Integer overflow is not a concern because the maximum number of triplets is:

$$100 \times 100 \times 100 = 1,000,000$$

which easily fits inside Go's int type.

Worked Examples

Example 1

Input:

a = [1]
b = [2]
c = [3]

Step 1: Compute parity counts

Number	Binary	Set Bits	Parity
1	001	1	Odd
2	010	1	Odd
3	011	2	Even

So we have:

Array	Even Count	Odd Count
a	0	1
b	0	1
c	1	0

Step 2: Apply formula

$$(aEven \times bEven \times cEven)$$

$$= 0 \times 0 \times 1 = 0$$

$$(aEven \times bOdd \times cOdd)$$

$$= 0 \times 1 \times 0 = 0$$

$$(aOdd \times bEven \times cOdd)$$

$$= 1 \times 0 \times 0 = 0$$

$$(aOdd \times bOdd \times cEven)$$

$$= 1 \times 1 \times 1 = 1$$

Final answer:

$$1$$

Example 2

Input:

a = [1, 1]
b = [2, 3]
c = [1, 5]

Step 1: Compute parity counts

Number	Binary	Set Bits	Parity
1	001	1	Odd
1	001	1	Odd

So for a:

Even	Odd
0	2

For b:

Number	Binary	Set Bits	Parity
2	010	1	Odd
3	011	2	Even

Even	Odd
1	1

For c:

Number	Binary	Set Bits	Parity
1	001	1	Odd
5	101	2	Even

Even	Odd
1	1

Step 2: Apply formula

$$0 \times 1 \times 1 = 0$$

$$0 \times 1 \times 1 = 0$$

$$2 \times 1 \times 1 = 2$$

$$2 \times 1 \times 1 = 2$$

Final answer:

$$0 + 0 + 2 + 2 = 4$$

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m + k)	Each array is scanned exactly once
Space	O(1)	Only a few counters are stored

The algorithm processes each number exactly one time to determine whether its set bit count is even or odd. No additional data structures proportional to input size are required, so the memory usage remains constant.

Test Cases

from typing import List

class Solution:
    def tripletCount(self, a: List[int], b: List[int], c: List[int]) -> int:
        def count_parity(nums: List[int]):
            even_count = 0
            odd_count = 0

            for num in nums:
                if num.bit_count() % 2 == 0:
                    even_count += 1
                else:
                    odd_count += 1

            return even_count, odd_count

        a_even, a_odd = count_parity(a)
        b_even, b_odd = count_parity(b)
        c_even, c_odd = count_parity(c)

        return (
            a_even * b_even * c_even +
            a_even * b_odd * c_odd +
            a_odd * b_even * c_odd +
            a_odd * b_odd * c_even
        )

sol = Solution()

assert sol.tripletCount([1], [2], [3]) == 1  # provided example 1

assert sol.tripletCount([1, 1], [2, 3], [1, 5]) == 4  # provided example 2

assert sol.tripletCount([0], [0], [0]) == 1  # XOR is 0, zero has even parity

assert sol.tripletCount([1], [1], [1]) == 0  # odd XOR odd XOR odd gives odd parity

assert sol.tripletCount([3], [5], [6]) == 1  # all numbers have even parity

assert sol.tripletCount([1, 2], [4, 7], [8, 15]) == 4  # mixed parity values

assert sol.tripletCount([0, 0], [0, 0], [0, 0]) == 8  # all triplets valid

assert sol.tripletCount([1, 1], [1, 1], [1, 1]) == 0  # all triplets invalid

assert sol.tripletCount([2], [2], [2]) == 0  # three odd parities produce odd result

assert sol.tripletCount([3, 5], [6, 9], [10, 12]) == 8  # all even parity numbers

Test Summary

Test	Why
[1], [2], [3]	Validates basic single-triplet case
[1,1], [2,3], [1,5]	Validates provided multi-triplet example
[0], [0], [0]	Ensures zero parity handled correctly
[1], [1], [1]	Tests all odd parity values
[3], [5], [6]	Tests all even parity values
Mixed parity arrays	Verifies formula combinations
All zeros	Ensures all triplets counted
All ones	Ensures no valid triplets
[2], [2], [2]	Confirms odd parity behavior
Large even parity mix	Tests multiple valid combinations

Edge Cases

Arrays Containing Zero

The number 0 has zero set bits, and zero is considered an even number. This can easily be overlooked if the implementation incorrectly assumes parity requires at least one set bit.

For example:

0 XOR 0 XOR 0 = 0

The result still has an even number of set bits, so the triplet is valid. The implementation handles this naturally because 0.bit_count() returns 0.

All Numbers Have Odd Parity

If every number in all three arrays contains an odd number of set bits, then every triplet contains three odd parities.

An odd number of odd terms produces odd parity overall, so no triplet should be counted.

This is a common logical pitfall because it is easy to incorrectly assume odd XOR odd always becomes even, forgetting there are three operands involved.

The formula correctly excludes this case.

Duplicate Values

The problem counts triplets by index combinations, not unique numeric values.

For example:

a = [1, 1]
b = [2]
c = [5]

Even though the numeric values repeat, there are still two distinct triplets because the indices differ.

The implementation correctly handles this because it counts frequencies based on array elements directly, not unique values.