We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Triplets That Can Form Two Arrays of Equal XOR

Number: 1553

Difficulty: Medium

Paid? No

Companies: Google, Amazon

Problem Description

Given an integer array arr, count the number of triplets (i, j, k) that satisfy 0 <= i < j <= k < arr.length and where the XOR of the subarray from arr[i] to arr[j-1] is equal to the XOR of the subarray from arr[j] to arr[k]. In other words, letting a = arr[i] ^ ... ^ arr[j-1] and b = arr[j] ^ ... ^ arr[k], count the number of triplets where a == b.

Key Insights

  • Using the properties of XOR, note that if a ^ b = 0 then a equals b.
  • Define a prefix XOR array such that prefix[k] = arr[0] XOR arr[1] XOR ... XOR arr[k-1].
  • The condition a == b is equivalent to prefix[i] == prefix[k+1], where i < k+1.
  • For any such pair (i, k+1) with equal prefix XOR, any index j with i < j <= k is valid; hence contribution to count is (k - i).
  • An O(n^2) solution is feasible given the constraint that the length of arr is at most 300.

Space and Time Complexity

Time Complexity: O(n^2) Space Complexity: O(n) for storing the prefix XOR array

Solution

We use a prefix XOR array to efficiently compute the XOR for any subarray. The key observation is that if we denote prefix[i] as the XOR of all elements before index i, then the XOR of the subarray from i to k is given by prefix[i] XOR prefix[k+1]. For the XOR for subarrays to be equal (i.e., a == b), we require prefix[i] == prefix[k+1]. For each pair of indices (i, k) that satisfy this condition, every index j with i < j <= k gives a valid triplet, contributing (k - i) to our answer. We iterate with two nested loops over possible starting and ending indices and update our running total of valid triplets accordingly.

Code Solutions

# Python solution

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        # Build prefix XOR array where prefix[i] = arr[0] ^ arr[1] ^ ... ^ arr[i-1]
        prefix = [0] * (n + 1)
        for i in range(1, n + 1):
            prefix[i] = prefix[i - 1] ^ arr[i - 1]
            
        count = 0
        # Iterate over all possible pairs (i, k)
        for i in range(n):
            for k in range(i + 1, n):
                # If prefix XOR from 0 to i equals from 0 to k+1,
                # then arr[i] ^ ... ^ arr[k] equals 0.
                if prefix[i] == prefix[k + 1]:
                    # All j such that i < j <= k are valid -> there are (k - i) choices
                    count += (k - i)
        return count
← Back to All Questions