1442. Count Triplets That Can Form Two Arrays of Equal XOR[Medium](Leetcode每日一题-2021.05.18)

本文主要是介绍1442. Count Triplets That Can Form Two Arrays of Equal XOR[Medium](Leetcode每日一题-2021.05.18)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem

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.

Constraints:

• 1 <= arr.length <= 300
• 1 <= arr[i] <= 10^8

Example1

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)

Example2

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

Example3

Input: arr = [2,3]
Output: 0

Example4

Input: arr = [1,3,5,7,9]
Output: 3

Example5

Input: arr = [7,11,12,9,5,2,7,17,22]
Output: 8

Solution

class Solution {
public:int countTriplets(vector<int>& arr) {vector<int> prefix_xor;prefix_xor.push_back(0);for(int i = 1;i<=arr.size();++i){prefix_xor.push_back(prefix_xor.back() ^ arr[i-1]);}int ret = 0;for(int i = 0;i<prefix_xor.size();++i){for(int j = i+1;j<prefix_xor.size();++j){if(prefix_xor[i] ^ prefix_xor[j] == 0)ret += j-i-1;}}return ret;}
};

这篇关于1442. Count Triplets That Can Form Two Arrays of Equal XOR[Medium](Leetcode每日一题-2021.05.18)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---