Skip to main content
Talentd

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

EasyPremiumFree 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 of 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 <= 100
  • 0 <= a[i], b[i], c[i] <= 100

Approach Overview

Problem Overview: You are given three arrays and need to count triplets (a, b, c) where one element is chosen from each array. A triplet is valid if the XOR value a ^ b ^ c contains an even number of set bits. The key challenge is recognizing that only the parity of the set bit count matters.

Approach 1: Brute Force Triplets (O(n * m * k) time, O(1) space)

Check every possible triplet by iterating through the three arrays using three nested loops. For each combination, compute x = a ^ b ^ c and count its set bits using a popcount operation. If the number of set bits is even, increment the answer. This approach is straightforward and helps verify correctness, but it becomes slow when arrays grow because the complexity multiplies across all three lengths.

Approach 2: Bit Parity Counting (O(n + m + k) time, O(1) space)

The optimal observation: the parity of set bits in an XOR equals the XOR of the individual parities. In other words, parity(popcount(a ^ b ^ c)) = pa ^ pb ^ pc, where pa, pb, and pc represent whether each number has an odd (1) or even (0) number of set bits. The result is even when this XOR equals 0.

First compute the set-bit parity of every number in each array. Count how many values have even parity and how many have odd parity. Then combine counts instead of enumerating triplets. Valid triplets occur when the XOR of the three parities equals 0, which happens for combinations like (even, even, even) or any case where exactly two are odd. Multiply the corresponding counts to get the total. This converts a triple nested iteration into simple counting.

This problem relies heavily on understanding XOR properties and bit-count parity. If XOR and popcount operations feel unfamiliar, reviewing bit manipulation fundamentals and parity tricks will make these patterns much easier to spot. Similar counting optimizations also appear in problems involving arrays and XOR-based constraints.

Recommended for interviews: Start by explaining the brute force enumeration to show the direct interpretation of the problem. Then introduce the parity insight that collapses the search space. Interviewers typically expect the parity-counting approach because it demonstrates strong understanding of XOR properties and efficient counting techniques.

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 TripletsO(n * m * k)O(1)Good for understanding the problem or when arrays are extremely small
Bit Parity CountingO(n + m + k)O(1)Optimal solution using XOR parity observation; works for large inputs

Video Solution

Counting Bits - Dynamic Programming - Leetcode 338 - Python • NeetCode • 159,557 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Triplets with Even XOR Set Bits I easy or hard?
Count Triplets with Even XOR Set Bits I is categorized as an Easy problem with a high acceptance rate. The main trick is recognizing the XOR parity property, which turns a brute-force O(n * m * k) search into a linear counting solution.
Count Triplets with Even XOR Set Bits I Python/Java solution
The implementation typically uses a popcount operation such as bin(x).count('1') in Python or Integer.bitCount(x) in Java to determine parity. After counting even and odd occurrences in each array, multiply the valid combinations to compute the total number of triplets.
How to solve Count Triplets with Even XOR Set Bits I in O(n)?
Compute the parity (even or odd number of set bits) for each value using a popcount operation. Count how many elements in each array have even parity and how many have odd parity. Valid triplets occur when pa ^ pb ^ pc equals 0, so combine the counts accordingly. This avoids iterating through all triplets.
What is the best approach for Count Triplets with Even XOR Set Bits I?
The best approach uses bit parity counting. Instead of checking every triplet, compute whether each number has an even or odd number of set bits. Because parity(popcount(a ^ b ^ c)) equals pa ^ pb ^ pc, you only need to count combinations where this XOR equals 0. This reduces the complexity to O(n + m + k).
Is Count Triplets with Even XOR Set Bits I asked at Google/Amazon/Meta?
Problems based on XOR parity and bit manipulation appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact question may vary, the underlying concept of using XOR properties and popcount parity to reduce complexity is a common interview pattern.
What data structure is used in Count Triplets with Even XOR Set Bits I?
The solution mainly relies on simple counters and bit manipulation operations. No complex data structure is required; you only track counts of numbers with even and odd set-bit parity in each array.
What is the time complexity of Count Triplets with Even XOR Set Bits I?
The optimal solution runs in O(n + m + k) time, where n, m, and k are the sizes of the three arrays. Each number is processed once to compute the parity of its set bits, and the final answer is derived using simple count combinations. Space complexity is O(1).

Ready to solve this problem?

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

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays