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

Count Triplets That Can Form Two Arrays of Equal XOR

Difficulty: Medium

Problem 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 a and b be defined as follows:

a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

Return the number of triplets (i, j, k) where a == b.

Key Insights

The XOR operation has properties that can be leveraged, such as a ^ a = 0 and a ^ 0 = a.
A prefix XOR array can be used to efficiently calculate the XOR of any subarray.
The problem can be solved by iterating over possible values of j and using a hashmap to keep track of the counts of prefix XOR values to find valid i and k.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Solution

To solve this problem, we use the following approach:

Create a prefix XOR array to store the cumulative XOR values.
For each possible j (the middle index), calculate the value of a using the prefix XOR.
Use a hashmap to count occurrences of prefix XOR values that match the calculated a.
For each k that satisfies the condition, increment the count based on how many times the prefix XOR that matches b has been seen.

Code Solutions

def countTriplets(arr):
    n = len(arr)
    prefix_xor = [0] * (n + 1)
    
    # Compute prefix XOR array
    for i in range(n):
        prefix_xor[i + 1] = prefix_xor[i] ^ arr[i]
    
    count = 0
    
    # Iterate over possible middle index j
    for j in range(1, n + 1):
        xor_a = prefix_xor[j - 1]  # a = XOR from arr[i] to arr[j-1]
        
        # Count occurrences of prefix_xor values
        xor_count = {}
        
        # Calculate b and count valid k's
        for k in range(j, n + 1):
            xor_b = prefix_xor[k] ^ xor_a  # b = XOR from arr[j] to arr[k]
            
            # Count how many times xor_b has been seen
            if xor_b in xor_count:
                count += xor_count[xor_b]
            
            # Update the count for the current prefix XOR
            if prefix_xor[k] in xor_count:
                xor_count[prefix_xor[k]] += 1
            else:
                xor_count[prefix_xor[k]] = 1
    
    return count

← Back to All Questions