LeetCode 1442. Count Triplets That Can Form Two Arrays of Equal XOR Solution in Java, C++, Python & More | Explanation + Code

Description

Given an array of integers 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]

Note that ^ denotes the bitwise-xor operation.

Return the number of triplets (i, j and k) Where a == b.

 

Example 1:

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)

Example 2:

Input: arr = [1,1,1,1,1]
Output: 10

 

Constraints:

• 1 <= arr.length <= 300
• 1 <= arr[i] <= 108

Solutions

Solution 1: Enumeration

According to the problem description, to find triplets (i, j, k) that satisfy a = b, which means s = a \oplus b = 0, we only need to enumerate the left endpoint i, and then calculate the prefix XOR sum s of the interval [i, k] with k as the right endpoint. If s = 0, then for any j ∈ [i + 1, k], the condition a = b is satisfied, meaning (i, j, k) is a valid triplet. There are k - i such triplets, which we can add to our answer.

After the enumeration is complete, we return the answer.

The time complexity is O(n²), where n is the length of the array arr. The space complexity is O(1).

PythonJavaC++GoTypeScriptRust

class Solution: def countTriplets(self, arr: List[int]) -> int: ans, n = 0, len(arr) for i, x in enumerate(arr): s = x for k in range(i + 1, n): s ^= arr[k] if s == 0: ans += k - i return ans(code-box)

class Solution { public int countTriplets(int[] arr) { int ans = 0, n = arr.length; for (int i = 0; i < n; ++i) { int s = arr[i]; for (int k = i + 1; k < n; ++k) { s ^= arr[k]; if (s == 0) { ans += k - i; } } } return ans; } }(code-box)

class Solution { public: int countTriplets(vector<int>& arr) { int ans = 0, n = arr.size(); for (int i = 0; i < n; ++i) { int s = arr[i]; for (int k = i + 1; k < n; ++k) { s ^= arr[k]; if (s == 0) { ans += k - i; } } } return ans; } };(code-box)

func countTriplets(arr []int) (ans int) { for i, x := range arr { s := x for k := i + 1; k < len(arr); k++ { s ^= arr[k] if s == 0 { ans += k - i } } } return }(code-box)

function countTriplets(arr: number[]): number { const n = arr.length; let ans = 0; for (let i = 0; i < n; ++i) { let s = arr[i]; for (let k = i + 1; k < n; ++k) { s ^= arr[k]; if (s === 0) { ans += k - i; } } } return ans; }(code-box)

impl Solution { pub fn count_triplets(arr: Vec<i32>) -> i32 { let mut ans = 0; let n = arr.len(); for i in 0..n { let mut s = arr[i]; for k in (i + 1)..n { s ^= arr[k]; if s == 0 { ans += (k - i) as i32; } } } ans } }(code-box)