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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5
6
7
8

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

Solution

Method 1 – Parity Counting with Bitwise XOR

Intuition

The number of set bits in the XOR of three numbers is even if the parity (even/odd) of the set bits in their XOR is 0. We can precompute the parity of set bits for all possible values and count how many numbers in each array have even or odd set bits. Then, for each combination, we check if the total parity is even.

Approach

  1. For each array, count how many numbers have even and odd set bits.
  2. For all combinations of parities (even/odd) for a, b, c, check if their XOR parity is even.
  3. Multiply the counts for valid combinations and sum them up.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int countTriplets(vector<int>& a, vector<int>& b, vector<int>& c) {
        auto parity = [](int x) { return __builtin_popcount(x) % 2; };
        int cntA[2] = {}, cntB[2] = {}, cntC[2] = {};
        for (int x : a) cntA[parity(x)]++;
        for (int x : b) cntB[parity(x)]++;
        for (int x : c) cntC[parity(x)]++;
        int ans = 0;
        for (int pa = 0; pa < 2; ++pa)
            for (int pb = 0; pb < 2; ++pb)
                for (int pc = 0; pc < 2; ++pc)
                    if ((pa ^ pb ^ pc) == 0)
                        ans += cntA[pa] * cntB[pb] * cntC[pc];
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func countTriplets(a, b, c []int) int {
    parity := func(x int) int {
        cnt := 0
        for x > 0 {
            cnt ^= x & 1
            x >>= 1
        }
        return cnt
    }
    cntA, cntB, cntC := [2]int{}, [2]int{}, [2]int{}
    for _, x := range a {
        cntA[parity(x)]++
    }
    for _, x := range b {
        cntB[parity(x)]++
    }
    for _, x := range c {
        cntC[parity(x)]++
    }
    ans := 0
    for pa := 0; pa < 2; pa++ {
        for pb := 0; pb < 2; pb++ {
            for pc := 0; pc < 2; pc++ {
                if pa^pb^pc == 0 {
                    ans += cntA[pa] * cntB[pb] * cntC[pc]
                }
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int countTriplets(int[] a, int[] b, int[] c) {
        int[] cntA = new int[2], cntB = new int[2], cntC = new int[2];
        for (int x : a) cntA[Integer.bitCount(x) % 2]++;
        for (int x : b) cntB[Integer.bitCount(x) % 2]++;
        for (int x : c) cntC[Integer.bitCount(x) % 2]++;
        int ans = 0;
        for (int pa = 0; pa < 2; pa++)
            for (int pb = 0; pb < 2; pb++)
                for (int pc = 0; pc < 2; pc++)
                    if ((pa ^ pb ^ pc) == 0)
                        ans += cntA[pa] * cntB[pb] * cntC[pc];
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun countTriplets(a: IntArray, b: IntArray, c: IntArray): Int {
        val cntA = IntArray(2)
        val cntB = IntArray(2)
        val cntC = IntArray(2)
        for (x in a) cntA[Integer.bitCount(x) % 2]++
        for (x in b) cntB[Integer.bitCount(x) % 2]++
        for (x in c) cntC[Integer.bitCount(x) % 2]++
        var ans = 0
        for (pa in 0..1)
            for (pb in 0..1)
                for (pc in 0..1)
                    if ((pa xor pb xor pc) == 0)
                        ans += cntA[pa] * cntB[pb] * cntC[pc]
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def countTriplets(self, a: list[int], b: list[int], c: list[int]) -> int:
        def parity(x: int) -> int:
            return bin(x).count('1') % 2
        cntA = [0, 0]
        cntB = [0, 0]
        cntC = [0, 0]
        for x in a:
            cntA[parity(x)] += 1
        for x in b:
            cntB[parity(x)] += 1
        for x in c:
            cntC[parity(x)] += 1
        ans = 0
        for pa in range(2):
            for pb in range(2):
                for pc in range(2):
                    if pa ^ pb ^ pc == 0:
                        ans += cntA[pa] * cntB[pb] * cntC[pc]
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

impl Solution {
    pub fn count_triplets(a: Vec<i32>, b: Vec<i32>, c: Vec<i32>) -> i32 {
        let mut cnt_a = [0; 2];
        let mut cnt_b = [0; 2];
        let mut cnt_c = [0; 2];
        for &x in &a {
            cnt_a[x.count_ones() as usize % 2] += 1;
        }
        for &x in &b {
            cnt_b[x.count_ones() as usize % 2] += 1;
        }
        for &x in &c {
            cnt_c[x.count_ones() as usize % 2] += 1;
        }
        let mut ans = 0;
        for pa in 0..2 {
            for pb in 0..2 {
                for pc in 0..2 {
                    if pa ^ pb ^ pc == 0 {
                        ans += cnt_a[pa] * cnt_b[pb] * cnt_c[pc];
                    }
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    countTriplets(a: number[], b: number[], c: number[]): number {
        const parity = (x: number) => x.toString(2).split('1').length % 2
        const cntA = [0, 0], cntB = [0, 0], cntC = [0, 0]
        for (const x of a) cntA[parity(x)]++
        for (const x of b) cntB[parity(x)]++
        for (const x of c) cntC[parity(x)]++
        let ans = 0
        for (let pa = 0; pa < 2; ++pa)
            for (let pb = 0; pb < 2; ++pb)
                for (let pc = 0; pc < 2; ++pc)
                    if ((pa ^ pb ^ pc) === 0)
                        ans += cntA[pa] * cntB[pb] * cntC[pc]
        return ans
    }
}

Complexity

  • ⏰ Time complexity: O(n + m + l) where n, m, l are the lengths of a, b, c (single pass through each array).
  • 🧺 Space complexity: O(1) for counters.