Skip to main content
Talentd

Count Triplets with Even XOR Set Bits II - Solution & Explanation

MediumPremiumFree on FleetCodeArrayBit Manipulation10 min readAsked at: Amazon
Practice this problem

Problem Statement

Given three integer arrays 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 <= 105
  • 0 <= a[i], b[i], c[i] <= 109

Approach Overview

Problem 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.

Solution

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Triplet EnumerationO(n^3)O(1)Useful for understanding the problem or validating logic on very small arrays
Parity Counting with Bit ManipulationO(n)O(1)Optimal solution for large inputs; reduces the problem to counting parity groups

Video Solution

Leetcode 3215. Count Triplets with Even XOR Set Bits II (xor) • LetsCode • 48 views views

Frequently Asked Questions

Is Count Triplets with Even XOR Set Bits II easy or hard?
The problem is typically classified as Medium difficulty. The brute-force idea is simple, but recognizing that only the parity of set bits matters requires deeper insight into XOR properties and bit manipulation.
Count Triplets with Even XOR Set Bits II Python/Java solution
Implement the optimized logic by iterating through the array, computing popcount for each number, and updating even and odd counters. After the scan, compute combinations C(even,3) and C(odd,2) * even. The same approach works across Python, Java, C++, Go, and TypeScript because it uses only basic bit operations.
How to solve Count Triplets with Even XOR Set Bits II in O(n)?
Compute p(x) = popcount(x) % 2 for each element. Maintain counts of numbers with even and odd bit parity. The number of valid triplets equals C(evenCount, 3) plus C(oddCount, 2) multiplied by evenCount. This works because the XOR of three numbers has even set bits when their parity XOR equals zero.
What is the best approach for Count Triplets with Even XOR Set Bits II?
The optimal approach uses bit manipulation and parity counting. Compute the parity of set bits for each number using popcount % 2, then count how many numbers have even or odd parity. Valid triplets occur when all three are even or when exactly two are odd and one is even. This reduces the problem to simple combinatorics in O(n) time and O(1) space.
Is Count Triplets with Even XOR Set Bits II asked at Google/Amazon/Meta?
Bit manipulation and XOR parity problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving XOR properties, popcount parity, or combinational counting are common because they test both bit-level reasoning and mathematical insight.
What data structure is used in Count Triplets with Even XOR Set Bits II?
The optimized solution does not require complex data structures. It relies on bit manipulation to compute popcount parity and simple integer counters to track how many numbers fall into even or odd parity groups.
What is the time complexity of Count Triplets with Even XOR Set Bits II?
The optimal solution runs in O(n) time because the array is scanned once to determine the parity of each element's set bits. After counting how many numbers have even and odd parity, the result is calculated using combination formulas. Space complexity remains O(1) since only two counters are stored.

Ready to solve this problem?

Practice Count Triplets with Even XOR Set Bits II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays