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 1442 with 17 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 1442 # by problem number
lcpy gen -s count_triplets_that_can_form_two_arrays_of_equal_xor # by problem name
arr.
We want to select three indices i, j and k where (0 <= i < j <= k < arr.length).
Let’s define a and b as follows:
a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]^ denotes the bitwise-xor operation.
Return the number of triplets (i, j and k) Where a == b.
Input: arr = [2,3,1,6,7]
Output: 4
Explanation: The triplets are (0,1,2), (0,2,2), (2,3,4) and (2,4,4)
Input: arr = [1,1,1,1,1]
Output: 10
1 <= arr.length <= 3001 <= arr[i] <= 10^8O(n) time?
class Solution:
# Time: O(n)
# Space: O(n)
def count_triplets(self, arr: list[int]) -> int:
# a == b means arr[i..k] xors to 0, i.e. pref[i] == pref[k + 1];
# each such pair (i, k) contributes k - i triplets (one per j in (i, k]).
total = 0
count = {0: 1}
index_sum = {0: 0}
prefix = 0
for m, value in enumerate(arr):
prefix ^= value
c = count.get(prefix, 0)
s = index_sum.get(prefix, 0)
total += c * m - s
count[prefix] = c + 1
index_sum[prefix] = s + m + 1
return total
| Time | Space |
|---|---|
| O(n) | O(n) |