Skip to content

3215. Count Triplets with Even XOR Set Bits II πŸ”’

Description

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 = 002.

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 = 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 <= 105
  • 0 <= a[i], b[i], c[i] <= 109

Solutions

Solution 1: Bit Manipulation

Thinking

We need triples whose XOR has an even popcount. \(n\le 10^5\) forbids enumerating triples. The parity of the XOR popcount is the parity of the three popcount parities.

Each array therefore collapses to two counts: popcount modulo \(2\). Enumerate the three parities and, when their sum is even, add the product of the three counts. After a linear pass the combination is \(O(1)\).

For two integers, the parity of the number of \(1\)s in the XOR result depends on the parity of the number of \(1\)s in the binary representations of the two integers.

We can use three arrays cnt1, cnt2, cnt3 to record the parity of the number of \(1\)s in the binary representations of each number in arrays a, b, c, respectively.

Then, we enumerate the parity of the number of \(1\)s in the binary representations of each number in the three arrays within the range \([0, 1]\). If the sum of the parity of the number of \(1\)s in the binary representations of three numbers is even, then the number of \(1\)s in the XOR result of these three numbers is also even. At this time, we multiply the combination of these three numbers and accumulate it into the answer.

Finally, return the answer.

The time complexity is \(O(n)\), where \(n\) is the length of arrays a, b, c. The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def tripletCount(self, a: List[int], b: List[int], c: List[int]) -> int:
        cnt1 = Counter(x.bit_count() & 1 for x in a)
        cnt2 = Counter(x.bit_count() & 1 for x in b)
        cnt3 = Counter(x.bit_count() & 1 for x in c)
        ans = 0
        for i in range(2):
            for j in range(2):
                for k in range(2):
                    if (i + j + k) & 1 ^ 1:
                        ans += cnt1[i] * cnt2[j] * cnt3[k]
        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
class Solution {
    public long tripletCount(int[] a, int[] b, int[] c) {
        int[] cnt1 = new int[2];
        int[] cnt2 = new int[2];
        int[] cnt3 = new int[2];
        for (int x : a) {
            ++cnt1[Integer.bitCount(x) & 1];
        }
        for (int x : b) {
            ++cnt2[Integer.bitCount(x) & 1];
        }
        for (int x : c) {
            ++cnt3[Integer.bitCount(x) & 1];
        }
        long ans = 0;
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                for (int k = 0; k < 2; ++k) {
                    if ((i + j + k) % 2 == 0) {
                        ans += 1L * cnt1[i] * cnt2[j] * cnt3[k];
                    }
                }
            }
        }
        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
class Solution {
public:
    long long tripletCount(vector<int>& a, vector<int>& b, vector<int>& c) {
        int cnt1[2]{};
        int cnt2[2]{};
        int cnt3[2]{};
        for (int x : a) {
            ++cnt1[__builtin_popcount(x) & 1];
        }
        for (int x : b) {
            ++cnt2[__builtin_popcount(x) & 1];
        }
        for (int x : c) {
            ++cnt3[__builtin_popcount(x) & 1];
        }
        long long ans = 0;
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                for (int k = 0; k < 2; ++k) {
                    if ((i + j + k) % 2 == 0) {
                        ans += 1LL * cnt1[i] * cnt2[j] * cnt3[k];
                    }
                }
            }
        }
        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
func tripletCount(a []int, b []int, c []int) (ans int64) {
    cnt1 := [2]int{}
    cnt2 := [2]int{}
    cnt3 := [2]int{}
    for _, x := range a {
        cnt1[bits.OnesCount(uint(x))%2]++
    }
    for _, x := range b {
        cnt2[bits.OnesCount(uint(x))%2]++
    }
    for _, x := range c {
        cnt3[bits.OnesCount(uint(x))%2]++
    }
    for i := 0; i < 2; i++ {
        for j := 0; j < 2; j++ {
            for k := 0; k < 2; k++ {
                if (i+j+k)%2 == 0 {
                    ans += int64(cnt1[i] * cnt2[j] * cnt3[k])
                }
            }
        }
    }
    return
}

 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
32
33
34
function tripletCount(a: number[], b: number[], c: number[]): number {
    const cnt1: [number, number] = [0, 0];
    const cnt2: [number, number] = [0, 0];
    const cnt3: [number, number] = [0, 0];
    for (const x of a) {
        ++cnt1[bitCount(x) & 1];
    }
    for (const x of b) {
        ++cnt2[bitCount(x) & 1];
    }
    for (const x of c) {
        ++cnt3[bitCount(x) & 1];
    }
    let ans = 0;
    for (let i = 0; i < 2; ++i) {
        for (let j = 0; j < 2; ++j) {
            for (let k = 0; k < 2; ++k) {
                if ((i + j + k) % 2 === 0) {
                    ans += cnt1[i] * cnt2[j] * cnt3[k];
                }
            }
        }
    }
    return ans;
}

function bitCount(i: number): number {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

Comments