Count Triplets That Can Form Two Arrays of Equal XOR – Leetcode Solution

In this post, we are going to solve the 1442. Count Triplets That Can Form Two Arrays of Equal XOR problem of Leetcode. This problem 1442. Count Triplets That Can Form Two Arrays of Equal XOR is a Leetcode medium level problem. Let’s see the code, 1442. Count Triplets That Can Form Two Arrays of Equal XOR – Leetcode Solution.

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.

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

Now, let’s see the code of 1442. Count Triplets That Can Form Two Arrays of Equal XOR – Leetcode Solution.

Count Triplets That Can Form Two Arrays of Equal XOR – Leetcode Solution

1442. Count Triplets That Can Form Two Arrays of Equal XOR – Solution in Java

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

1442. Count Triplets That Can Form Two Arrays of Equal XOR – Solution in C++

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

1442. Count Triplets That Can Form Two Arrays of Equal XOR – Solution in Python

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        res = 0
        for i in range(len(arr)-1):
            xor = 0
            for j in range(i, len(arr)):
                xor ^= arr[j]
                if xor == 0:
                    res += j-i # len-1
        return res

Note: This problem 1442. Count Triplets That Can Form Two Arrays of Equal XOR is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.

Leave a Comment

Your email address will not be published. Required fields are marked *