a, b, and c, return the number of triplets (a[i], b[j], c[k]), such that the bitwise XOR between the elements of each triplet has an even number of set bits.
Example 1:
Input: a = [1], b = [2], c = [3]
Output: 1
Explanation:
The only triplet is (a[0], b[0], c[0]) and their XOR is: 1 XOR 2 XOR 3 = 002.
Example 2:
Input: a = [1,1], b = [2,3], c = [1,5]
Output: 4
Explanation:
Consider these four triplets:
(a[0], b[1], c[0]): 1 XOR 3 XOR 1 = 0112(a[1], b[1], c[0]): 1 XOR 3 XOR 1 = 0112(a[0], b[0], c[1]): 1 XOR 2 XOR 5 = 1102(a[1], b[0], c[1]): 1 XOR 2 XOR 5 = 1102
Constraints:
1 <= a.length, b.length, c.length <= 1050 <= a[i], b[i], c[i] <= 109Problem Overview: Given an array of integers, count triplets (i, j, k) such that the XOR of the three numbers contains an even number of set bits. The challenge is recognizing how XOR interacts with bit counts and reducing the brute-force triplet search.
Approach 1: Brute Force Triplet Enumeration (O(n3) time, O(1) space)
Check every triplet (i, j, k) with three nested loops. For each combination compute x = nums[i] ^ nums[j] ^ nums[k] and count its set bits using popcount. If the number of set bits is even, increment the answer. This approach is straightforward and useful for validating logic on small inputs, but it becomes impractical for large arrays because the number of triplets grows as n^3. The method mainly demonstrates the direct application of Bit Manipulation operations.
Approach 2: Parity Observation with Counting (O(n) time, O(1) space)
The key observation: the parity of the number of set bits in a ^ b ^ c depends only on the parity of set bits in each number. Let p(x) = popcount(x) % 2. Then popcount(a ^ b ^ c) % 2 = p(a) ^ p(b) ^ p(c). For the XOR to contain an even number of set bits, this value must equal 0. That means either all three numbers have even bit parity, or exactly two numbers have odd parity and one has even parity.
Scan the array once and compute p(x) for each element using a popcount operation from bit manipulation. Maintain counts evenCount and oddCount. Valid triplets come from two patterns:
C(evenCount, 3) → all numbers have even bit parity.
C(oddCount, 2) * evenCount → two odd-parity numbers and one even-parity number.
This reduces the entire computation to simple combinatorics after a single pass through the array. Only two counters are stored, so the space complexity stays constant. The idea combines parity analysis with counting patterns often used in Array problems.
Recommended for interviews: Interviewers expect the parity-based counting approach. The brute force solution shows understanding of XOR and set bit counting, but the optimized solution demonstrates the real insight: only the parity of popcount matters. Once you convert numbers into parity buckets, the triplet counting becomes a small combinatorics problem with linear time complexity.
For two integers, the parity of the number of 1s in the XOR result depends on the parity of the number of 1s in the binary representations of the two integers.
We can use three arrays cnt1, cnt2, cnt3 to record the parity of the number of 1s in the binary representations of each number in arrays a, b, c, respectively.
Then, we enumerate the parity of the number of 1s in the binary representations of each number in the three arrays within the range [0, 1]. If the sum of the parity of the number of 1s in the binary representations of three numbers is even, then the number of 1s in the XOR result of these three numbers is also even. At this time, we multiply the combination of these three numbers and accumulate it into the answer.
Finally, return the answer.
The time complexity is O(n), where n is the length of arrays a, b, c. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Triplet Enumeration | O(n^3) | O(1) | Useful for understanding the problem or validating logic on very small arrays |
| Parity Counting with Bit Manipulation | O(n) | O(1) | Optimal solution for large inputs; reduces the problem to counting parity groups |
Leetcode 3215. Count Triplets with Even XOR Set Bits II (xor) • LetsCode • 34 views views
Practice Count Triplets with Even XOR Set Bits II with our built-in code editor and test cases.
Practice on FleetCode