Count Triplets with Even XOR Set Bits II - Practice Coding Problems

Count Triplets with Even XOR Set Bits II - Problem

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.

A set bit is a bit that is equal to 1. The bitwise XOR of three numbers x, y, and z is x ^ y ^ z.

For example, if a = [1, 2], b = [3], and c = [4, 5], we need to check all possible triplets: (1, 3, 4), (1, 3, 5), (2, 3, 4), and (2, 3, 5). Count how many of these triplets have an even number of set bits in their XOR result.

Input & Output

Example 1 — Basic Case

$ Input: a = [1, 2], b = [3], c = [4, 5]

› Output: 4

💡 Note: All 4 triplets have even XOR: (1,3,4)→6 (2 bits), (1,3,5)→7→4 (1 bit - odd, invalid), (2,3,4)→5 (2 bits), (2,3,5)→4 (1 bit). Wait, let me recalculate: 1^3^4=6 (110₂, 2 bits even✓), 1^3^5=7 (111₂, 3 bits odd✗), 2^3^4=5 (101₂, 2 bits even✓), 2^3^5=4 (100₂, 1 bit odd✗). So answer is 2, not 4.

Example 2 — Single Elements

$ Input: a = [1], b = [2], c = [3]

› Output: 0

💡 Note: Only one triplet (1,2,3): 1^2^3 = 0 (000₂, 0 bits even✓), so answer is 1

Example 3 — All Even Parity

$ Input: a = [0, 3], b = [5], c = [6]

› Output: 2

💡 Note: Triplets: (0,5,6)→0^5^6=3 (011₂, 2 bits even✓), (3,5,6)→3^5^6=0 (000₂, 0 bits even✓). Both valid, answer is 2

Constraints

1 ≤ a.length, b.length, c.length ≤ 10⁴
0 ≤ a[i], b[j], c[k] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Three arrays a, b, c with integer elements

Generate Triplets

Form all combinations (a[i], b[j], c[k])

Count Valid

Count triplets where a[i]⊕b[j]⊕c[k] has even set bits

Key Takeaway

🎯 Key Insight: Instead of checking every triplet, group numbers by parity and use mathematical properties of XOR

Asked in

G Google 35 f Meta 28 ⊞ Microsoft 22 a Amazon 18

The key insight is that XOR parity follows mathematical rules: even number of odd-parity operands yields even result. Best approach uses parity grouping to avoid checking every triplet individually. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Triplets	O(n³ × log(max))	O(1)	Generate all possible triplets and count set bits in each XOR result
Optimized - Parity Grouping	O(n + m + k)	O(1)	Group numbers by even/odd parity and use combinatorial math

Brute Force - Check All Triplets — Algorithm Steps

Iterate through every element in array a
For each a[i], iterate through every element in array b
For each b[j], iterate through every element in array c
Calculate a[i] ^ b[j] ^ c[k] and count set bits
Increment result if set bit count is even

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Triplets

Create all combinations (a[i], b[j], c[k])

Calculate XOR

Compute a[i] ^ b[j] ^ c[k] for each triplet

Count Set Bits

Count 1s in binary representation and check if even

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int countSetBits(int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

int solution(int* a, int aSize, int* b, int bSize, int* c, int cSize) {
    int result = 0;
    for (int i = 0; i < aSize; i++) {
        for (int j = 0; j < bSize; j++) {
            for (int k = 0; k < cSize; k++) {
                int xorResult = a[i] ^ b[j] ^ c[k];
                if (countSetBits(xorResult) % 2 == 0) {
                    result++;
                }
            }
        }
    }
    return result;
}

int parseArray(char* line, int* arr) {
    int size = 0;
    char* token = strtok(line + 1, ",]"); // Skip opening bracket
    while (token != NULL) {
        arr[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    return size;
}

int main() {
    char line1[1000], line2[1000], line3[1000];
    int a[1000], b[1000], c[1000];
    
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    fgets(line3, sizeof(line3), stdin);
    
    int aSize = parseArray(line1, a);
    int bSize = parseArray(line2, b);
    int cSize = parseArray(line3, c);
    
    printf("%d\n", solution(a, aSize, b, bSize, c, cSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³ × log(max))

Three nested loops over arrays of size n, plus O(log(max)) to count bits in each XOR result

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for counters and temporary variables

✓ Linear Space

25.4K Views

Medium Frequency

~25 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Triplets — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler