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 <= 1050 <= a[i], b[i], c[i] <= 109For two integers, the parity of the number of 1s in the XOR result depends on the parity of the number of 1s in the binary representations of the two integers.
We can use three arrays cnt1, cnt2, cnt3 to record the parity of the number of 1s in the binary representations of each number in arrays a, b, c, respectively.
Then, we enumerate the parity of the number of 1s 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 1s in the binary representations of three numbers is even, then the number of 1s 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).
Java
C++
Go
TypeScript
Count Triplets That Can Form Two Arrays of Equal XOR - Leetcode 1442 - Python • NeetCodeIO • 10,045 views views
Watch 9 more video solutions →Practice Count Triplets with Even XOR Set Bits II with our built-in code editor and test cases.
Practice on FleetCode