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

Count Triplets with Even XOR Set Bits I - 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 of the elements of each triplet has an even number of set bits.

A set bit is a bit that is equal to 1. The XOR operation combines three numbers: a[i] ^ b[j] ^ c[k]. Count how many bits are 1 in the result - if this count is even, include the triplet in your answer.

Input & Output

Example 1 — Basic Case

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

› Output: 4

💡 Note: All 4 triplets work: (2,3,1)→0 (even), (2,4,2)→0 (even), (1,3,2)→0 (even), (1,4,1)→4 (even)

Example 2 — Single Elements

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

› Output: 0

💡 Note: Only triplet is (1,2,3): 1^2^3=0, which has 0 set bits (even), so result is 1

Example 3 — All Same Parity

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

› Output: 0

💡 Note: All numbers have odd set bits. odd^odd^odd=odd, so no valid triplets

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Three arrays with various integers

XOR Operation

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

Count Set Bits

Count 1s in binary representation and check if even

Key Takeaway

🎯 Key Insight: XOR parity can be predicted mathematically without checking every combination

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that XOR parity follows mathematical rules: numbers with even set bits XORed in certain combinations always yield even results. The optimized approach groups numbers by parity and uses multiplication to count valid combinations. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Count by Parity	O(n)	O(1)	Group numbers by even/odd set bit count and use mathematical combinations
Brute Force - Try All Triplets	O(n³)	O(1)	Check every possible combination of three elements

Optimized - Count by Parity — Algorithm Steps

Count numbers with even/odd set bits in each array
Calculate combinations: (evenA × evenB × evenC) + (evenA × oddB × oddC) + (oddA × evenB × oddC) + (oddA × oddB × evenC)

Visualization

Tap to expand

Step-by-Step Walkthrough

Group by Parity

Count even/odd set bit numbers in each array

Calculate Combinations

Use math to count valid triplet combinations

Sum Results

Add all valid combination counts

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) {
    // Count numbers with even/odd set bits in each array
    int evenA = 0, oddA = 0;
    for (int i = 0; i < aSize; i++) {
        if (countSetBits(a[i]) % 2 == 0) {
            evenA++;
        } else {
            oddA++;
        }
    }
    
    int evenB = 0, oddB = 0;
    for (int i = 0; i < bSize; i++) {
        if (countSetBits(b[i]) % 2 == 0) {
            evenB++;
        } else {
            oddB++;
        }
    }
    
    int evenC = 0, oddC = 0;
    for (int i = 0; i < cSize; i++) {
        if (countSetBits(c[i]) % 2 == 0) {
            evenC++;
        } else {
            oddC++;
        }
    }
    
    // Count valid combinations
    return (evenA * evenB * evenC) + (evenA * oddB * oddC) + (oddA * evenB * oddC) + (oddA * oddB * evenC);
}

int main() {
    char line[1000];
    int a[100], b[100], c[100];
    int aSize = 0, bSize = 0, cSize = 0;
    
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line + 1, ",]");
    while (token) {
        a[aSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    token = strtok(line + 1, ",]");
    while (token) {
        b[bSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    token = strtok(line + 1, ",]");
    while (token) {
        c[cSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(a, aSize, b, bSize, c, cSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through each array to count parities

✓ Linear Growth

Space Complexity

O(1)

Only storing parity counts, no extra data structures

✓ Linear Space

12.0K Views

Medium Frequency

~15 min Avg. Time

450 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

Optimized - Count by Parity — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler