1442. Count Triplets That Can Form Two Arrays of Equal XOR

LeetCode 1442. Count Triplets That Can Form Two Arrays of Equal XOR

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] <= 10^8

Tags

Array, Math, Bit Manipulation

Solution

Solution 1:

This problem is equivalent to "search for a sub-array whose elements XOR = 0", since $a = b \equiv a\oplus b = 0$ . Thus, we can build a prefix-xor array first, then traverse this array with O(n^2) complexity to find all sub-arrays of length x whose xor is 0, and add x-1 onto the result counter.

Solution 2:

We can use hash tables to avoid to find i to save time. Based on the observation that $(k - i_1) + (k - i_2) + ... + (k - i_m) = m*k - (i_1+i_2+...+i_m)$ , we apply 2 hash tables to record both times of occurrence of a certain prefix-xor, and the sum of indices i, which is equal to k.

Complexity

Solution 1:

• Time complexity: $O(n^2)$

• Space complexity: $O(n)$

Solution 2:

• Time complexity: $O(n)$

• Space complexity: $O(n)$

Code

Solution 1:

func countTriplets(arr []int) int {
	ans, s, count, total := 0, 0, map[int]int{}, map[int]int{} // index:xor, index:count_i
	for k, v := range arr {
		if m, ok := count[s^v]; ok {
			ans += m*k - total[s^v]
		}
		count[s]++
		total[s] += k
		s ^= v
	}
	return ans
}

Solution 2:

func countTriplets(arr []int) int {
   ans, prefix := 0, make([]int, len(arr)+1)
   for i, v := range arr {
      prefix[i+1] = prefix[i] ^ v
   }
   for i := 1; i < len(arr); i++ {
      for k := i + 1; k <= len(arr); k++ {
         if prefix[i-1] == prefix[k] { // prefix[i-1]^prefix[k] == 0
            ans += k - i // k-(i-1)+1
         }
      }
   }
   return ans
}

Reference

1. 形成两个异或相等数组的三元组数目

2. 新手篇 -- 浅入深出系列1