Skip to content

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

SourceWeekly Contest 188 Q2DifficultyMediumRating1524

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

Thinking

\(a=b\) iff the XOR of \([i,k]\) is \(0\), in which case any \(j\in(i,k]\) works (\(k-i\) triples). \(n\le 300\), so enumerate \(i\) and \(k\) while maintaining the running XOR.

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 \in [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^2)\), where \(n\) is the length of the array \(\textit{arr}\). The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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
    }
}

Comments