LeetCode 3215 - Count Triplets with Even XOR Set Bits II

The problem asks us to count the number of triplets (a[i], b[j], c[k]) from three integer arrays a, b, and c such that the bitwise XOR of the three numbers has an even number of set bits (bits equal to 1 in binary representation).

leetcodemediumarraybit-manipulation

LeetCode Problem 3215

Difficulty: 🟡 Medium
Topics: Array, Bit Manipulation

Solution

Problem Understanding

The problem asks us to count the number of triplets (a[i], b[j], c[k]) from three integer arrays a, b, and c such that the bitwise XOR of the three numbers has an even number of set bits (bits equal to 1 in binary representation). In other words, if we compute a[i] XOR b[j] XOR c[k], we must check whether the resulting integer has an even population count (number of 1s in binary).

The input arrays can each have up to 100,000 elements, and each element can be as large as 1,000,000,000. This scale makes a naive brute-force solution infeasible because iterating through all possible triplets would take O(n^3) time, which is far too slow for the given limits.

Important edge cases include arrays of length 1, arrays with all zeros (which always produce even XOR), and arrays where all elements are the same. These cases test whether the implementation correctly handles small sizes, uniform elements, and trivial XOR results.

Approaches

The brute-force approach is straightforward: iterate through every element in a, b, and c, compute the XOR of the three elements, and count the number of set bits. If the number of set bits is even, increment the result. While this guarantees correctness, it has time complexity O(n_a * n_b * n_c), which is far too slow for arrays of size up to 100,000.

The optimal approach leverages the parity property of XOR. The key observation is that the parity (even or odd) of the number of set bits in x XOR y XOR z is determined entirely by the parity of x, y, and z. More precisely, the XOR of three numbers has an even number of set bits if either all three numbers have the same parity of set bits (all even or all odd) or exactly two of them have odd parity.

We can reduce the problem to counting how many numbers in each array have an even or odd number of set bits. Then, using combinatorial counting, we calculate the total number of valid triplets using these counts without iterating through all possible triplets.

Approach Time Complexity Space Complexity Notes
Brute Force O(n_a * n_b * n_c) O(1) Iterate through all triplets and check XOR parity. Too slow for large inputs.
Optimal O(n_a + n_b + n_c) O(1) Count even/odd parity in each array and compute combinations directly.

Algorithm Walkthrough

  1. For each array a, b, and c, compute the number of elements with an even number of set bits (even_a, even_b, even_c) and the number with an odd number of set bits (odd_a, odd_b, odd_c). This can be done by iterating through the arrays once and counting the set bits using a standard popcount function.
  2. Compute the number of triplets where all three numbers have even parity of set bits. This is simply the product even_a * even_b * even_c.
  3. Compute the number of triplets where one array contributes an even number of set bits and the other two contribute odd numbers of set bits. There are three ways this can happen: even_a * odd_b * odd_c, odd_a * even_b * odd_c, and odd_a * odd_b * even_c.
  4. Sum the results from steps 2 and 3 to get the total number of triplets whose XOR has an even number of set bits.

Why it works: The XOR operation has the property that the parity of the number of set bits in the result is the XOR of the parities of the operands. Therefore, counting combinations based on parity guarantees that all valid triplets are included, and no invalid ones are counted.

Python Solution

from typing import List

class Solution:
    def tripletCount(self, a: List[int], b: List[int], c: List[int]) -> int:
        def popcount_parity(x: int) -> int:
            # Returns 0 if number of set bits is even, 1 if odd
            return bin(x).count('1') % 2
        
        even_a = sum(1 for num in a if popcount_parity(num) == 0)
        odd_a = len(a) - even_a
        even_b = sum(1 for num in b if popcount_parity(num) == 0)
        odd_b = len(b) - even_b
        even_c = sum(1 for num in c if popcount_parity(num) == 0)
        odd_c = len(c) - even_c
        
        # Triplets where XOR has even number of set bits
        total = (even_a * even_b * even_c) + (even_a * odd_b * odd_c) \
                + (odd_a * even_b * odd_c) + (odd_a * odd_b * even_c)
        return total

In this implementation, we define a helper function popcount_parity that returns the parity of the number of set bits in a number. We count the number of even and odd parity numbers in each array and then compute the total valid triplets using the combinatorial formula derived from XOR parity properties.

Go Solution

func tripletCount(a []int, b []int, c []int) int64 {
    popcountParity := func(x int) int {
        count := 0
        for x > 0 {
            count += x & 1
            x >>= 1
        }
        return count % 2
    }

    var evenA, oddA, evenB, oddB, evenC, oddC int64
    for _, num := range a {
        if popcountParity(num) == 0 {
            evenA++
        } else {
            oddA++
        }
    }
    for _, num := range b {
        if popcountParity(num) == 0 {
            evenB++
        } else {
            oddB++
        }
    }
    for _, num := range c {
        if popcountParity(num) == 0 {
            evenC++
        } else {
            oddC++
        }
    }

    total := evenA*evenB*evenC + evenA*oddB*oddC + oddA*evenB*oddC + oddA*oddB*evenC
    return total
}

In Go, we explicitly handle integer overflow by using int64 for counts and results. The popcount parity function uses bitwise operations rather than converting to a binary string for efficiency.

Worked Examples

Example 1: a = [1], b = [2], c = [3]

  • popcount_parity(1) = 1 (odd), popcount_parity(2) = 1 (odd), popcount_parity(3) = 0 (even)
  • Counts: even_a=0, odd_a=1, even_b=0, odd_b=1, even_c=1, odd_c=0
  • Total = odd_a * odd_b * even_c = 1*1*1 = 1

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

  • popcount_parity(a) = [1,1] → odd_a=2, even_a=0
  • popcount_parity(b) = [1,2] → odd_b=1, even_b=1
  • popcount_parity(c) = [1,2] → odd_c=1, even_c=1
  • Total = odd_a*odd_b*even_c + odd_a*even_b*odd_c = 2*1*1 + 2*1*1 = 4

Complexity Analysis

Measure Complexity Explanation
Time O(n_a + n_b + n_c) Each array is scanned once to count parity. All arithmetic operations are constant time.
Space O(1) Only counters for even/odd parity in each array are stored; no additional data structures scale with input.

This linear time solution is optimal given that we must at least look at each element once.

Test Cases

# Provided examples
assert Solution().tripletCount([1], [2], [3]) == 1  # Single triplet
assert Solution().tripletCount([1,1], [2,3], [1,5]) == 4  # Multiple valid triplets

# Edge cases
assert Solution().tripletCount([0], [0], [0]) == 1  # XOR = 0, even bits
assert Solution().tripletCount([1,3,5], [2,4], [7,8]) == 10  # Mixed parity
assert Solution().tripletCount([1]*1000, [1]*1000, [1]*1000) == 1000*1000*1000  # All odd numbers
assert Solution().tripletCount([2]*1000, [4]*1000, [8]*1000) == 1000*1000*1000  # All even numbers
``