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.

Description Hints 4 Solution Video 11:31

3215. Count Triplets with Even XOR Set Bits II

Medium62.0% acceptance1 companyPremium elsewhere, free here

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 = 00₂.

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 = 011₂
(a[1], b[1], c[0]): 1 XOR 3 XOR 1 = 011₂
(a[0], b[0], c[1]): 1 XOR 2 XOR 5 = 110₂
(a[1], b[0], c[1]): 1 XOR 2 XOR 5 = 110₂

Constraints:

1 <= a.length, b.length, c.length <= 10⁵
0 <= a[i], b[i], c[i] <= 10⁹

Asked at 1 company

Amazon

Topics

Array Bit Manipulation

Hints open one at a time

Hint 1

If x and y both have an even number of set bits, how many set bits do their XOR have?

Hint 2

If exactly one of x and y has an even number of set bits, how many set bits do their XOR have?

Hint 3

Conclude that if the XOR of three elements would have an even number of set bits, an even number of them (0 or 2) should have an odd number of set bits!

Hint 4

For each array count the number of elements that have even set bits and also count the ones that have odd set bits.

11:31

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1]
[2]
[3]

Input

[1,1]
[2,3]
[1,5]

Your code is saved on this device.Solution