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.

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 <= 10^5
  • 0 <= a[i], b[i], c[i] <= 10^9

Solution

Method 1 – Prefix XOR and Parity Counting

Intuition

For each triplet (a[i], b[j], c[k]), the XOR of the three numbers has an even number of set bits if the parity of set bits in a[i] ^ b[j] ^ c[k] is even. We can precompute the parity of set bits for all possible values and use prefix XOR and counting to efficiently count valid triplets.

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:
    long long countTriplets(vector<int>& a, vector<int>& b, vector<int>& c) {
        auto parity = [](int x) { return __builtin_popcount(x) % 2; };
        long long 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)]++;
        long long 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) int64 {
    parity := func(x int) int {
        cnt := 0
        for x > 0 {
            cnt ^= x & 1
            x >>= 1
        }
        return cnt
    }
    cntA, cntB, cntC := [2]int64{}, [2]int64{}, [2]int64{}
    for _, x := range a {
        cntA[parity(x)]++
    }
    for _, x := range b {
        cntB[parity(x)]++
    }
    for _, x := range c {
        cntC[parity(x)]++
    }
    var ans int64
    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 long countTriplets(int[] a, int[] b, int[] c) {
        long[] cntA = new long[2], cntB = new long[2], cntC = new long[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]++;
        long 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): Long {
        val cntA = LongArray(2)
        val cntB = LongArray(2)
        val cntC = LongArray(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 = 0L
        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>) -> i64 {
        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 = 0i64;
        for pa in 0..2 {
            for pb in 0..2 {
                for pc in 0..2 {
                    if pa ^ pb ^ pc == 0 {
                        ans += cnt_a[pa] as i64 * cnt_b[pb] as i64 * cnt_c[pc] as i64;
                    }
                }
            }
        }
        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 = 0n
        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 += BigInt(cntA[pa]) * BigInt(cntB[pb]) * BigInt(cntC[pc])
        return Number(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.