Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 3199 with 21 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 3199 # by problem number
lcpy gen -s count_triplets_with_even_xor_set_bits_i # by problem name
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.
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 = 00_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 = 011_2
- (a[1], b[1], c[0]): 1 XOR 3 XOR 1 = 011_2
- (a[0], b[0], c[1]): 1 XOR 2 XOR 5 = 110_2
- (a[1], b[0], c[1]): 1 XOR 2 XOR 5 = 110_2
class Solution:
# Time: O(len(a) + len(b) + len(c))
# Space: O(1)
def triplet_count(self, a: list[int], b: list[int], c: list[int]) -> int:
cnt1 = [0, 0]
cnt2 = [0, 0]
cnt3 = [0, 0]
for x in a:
cnt1[x.bit_count() & 1] += 1
for x in b:
cnt2[x.bit_count() & 1] += 1
for x in c:
cnt3[x.bit_count() & 1] += 1
ans = 0
for i in range(2):
for j in range(2):
for k in range(2):
if (i + j + k) % 2 == 0:
ans += cnt1[i] * cnt2[j] * cnt3[k]
return ans
| Time | Space |
|---|---|
| O(len(a) + len(b) + len(c)) | O(1) |