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

MediumBit ManipulationArrayHash TableMathPrefix Sum
Leetcode Link

Problem Description

The LeetCode problem requires us to find the number of triplets (i, j, k) in an integer array where (0 <= i < j <= k < arr.length). For each triplet, we define two values, a and b, where a is the bitwise XOR of arr[i] through arr[j - 1], and b is the bitwise XOR of arr[j] through arr[k]. Our goal is to count how many such triplets yield a == b.

Intuition

To solve this problem, we begin by thinking about the properties of XOR. A key insight is that the XOR operation is both associative and commutative, which implies that the order of elements does not change the result of the XOR. Another insight is that XOR-ing a number with itself yields zero. By taking advantage of this, we can precompute the XOR of all elements up to k for every index k in the array, storing the results in a prefix XOR array pre.

This precomputation allows us to find the XOR of any subarray in constant time. For any two indices i and j, the XOR of the subarray from i to j-1 can be obtained by pre[j] ^ pre[i]. This is because pre[j] contains the XOR of all elements up to j-1 and pre[i] contains the XOR of all elements up to i-1. So, when we XOR these two, all the elements before i are nullified, leaving just the XOR of the subarray.

The next step is to check every possible combination of (i, j, k). This requires three nested loops. For each triplet:

  1. We calculate a as the XOR of the subarray from i to j-1.
  2. We calculate b as the XOR of the subarray from j to k.
  3. We check if a is equal to b.

If a equals b, we increment our answer count (ans). After considering all possible triplets, ans will contain the total number of triplets for which a equals b.

The solution's time complexity is O(n^3) due to the use of three nested loops, which might not be the most efficient for large input arrays. However, for the purpose of understanding the problem, this brute force approach shows the direct application of XOR properties and precomputed prefix sums to solve the problem.

Learn more about Math and Prefix Sum patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Solution Approach

In the implementation of the solution for counting the triplets that satisfy a == b where a and b are defined through the bitwise XOR operation, we use the prefix sum pattern with a slight tweak - using XOR instead of addition.

The steps of the implementation include:

  1. Initialization:

    • Calculate the length of the input array arr and denote it as n.
    • Initialize a list pre with a length of n + 1 to store the prefix XOR values. The pre[i] will store the XOR of all elements from the beginning of the array up to the i-1th index.

  2. Precomputation:

    • We calculate the prefix XOR sequence by iterating through the input array and performing the XOR operation for each element. The pre[0] is set to be 0 as a base case since XOR with 0 gives us the number itself, which starts our sequence.

  3. Triplets Counting:

    • After the precomputation step, we iterate over all potential starting indices i for the array segment a.
    • For each i, iterate over all potential starting indices j where j > i for the array segment b. Note that j can also be the ending index of segment a.
    • For each pair (i, j), iterate over all possible ending indices k for the segment b where k >= j.
      • Compute a as pre[j] ^ pre[i] which gives the XOR of the subarray from i to j-1.
      • Compute b as pre[k + 1] ^ pre[j] which gives the XOR of the subarray from j to k.
      • If a equals b, increment the counter ans.

  4. Return the result:

    • After iterating through all triplets, the counter ans holds the number of triplets satisfying a == b. Return ans.

This brute-force algorithm uses the concept of prefix sums along with the properties of XOR to solve the problem in a straightforward way. The primary data structure used here is the array for storing prefix XORs. The pattern utilized is a classic computational geometry approach to handle subarray or subrange queries efficiently by preparation combined with a brute-force enumeration of triplets.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Example Walkthrough

Let's illustrate the solution approach with an example. Suppose we have the following array:

1arr = [3, 10, 5, 25, 2, 8]

Following the solution approach:

  1. Initialization:

    • The length of the array n is 6.
    • We initialize a list pre with length n + 1 to store the prefix XOR values. Thus, pre has 7 elements.

  2. Precomputation:

    • We set pre[0] to 0. We then iterate over the array to fill in the rest of the pre array with prefix XOR values: 
      1arr: [ 3, 10, 5, 25, 2, 8 ]
2pre: [ 0, 3, 9, 12, 21, 23, 31 ]

  3. Triplets Counting:

    • We iterate over all combinations of i, j, and k to find all possible (i, j, k) triplets:
      • For i = 0, j = 1, and k = 2, we have:
        • a = pre[j] ^ pre[i] = pre[1] ^ pre[0] = 3 ^ 0 = 3
        • b = pre[k + 1] ^ pre[j] = pre[3] ^ pre[1] = 12 ^ 3 = 9
        • Since a is not equal to b, we do not increment ans.
      • For i = 0, j = 2, and k = 3, we have:
        • a = pre[j] ^ pre[i] = pre[2] ^ pre[0] = 9 ^ 0 = 9
        • b = pre[k + 1] ^ pre[j] = pre[4] ^ pre[2] = 21 ^ 9 = 12
        • Since a is not equal to b, we do not increment ans.
      • We continue this process for all possible i, j, and k.
      • For i = 1, j = 3, and k = 5, we find that:
        • a = pre[j] ^ pre[i] = pre[3] ^ pre[1] = 12 ^ 3 = 9
        • b = pre[k + 1] ^ pre[j] = pre[6] ^ pre[3] = 31 ^ 12 = 19
        • a is not equal to b, so ans remains unchanged.
      • Finally, upon reaching i = 1, j = 4, and k = 5, we get:
        • a = pre[j] ^ pre[i] = pre[4] ^ pre[1] = 21 ^ 3 = 22
        • b = pre[k + 1] ^ pre[j] = pre[6] ^ pre[4] = 31 ^ 21 = 10
        • Once again, a is not equal to b.
      • This iterative process is performed for all combinations to search for a == b.

  4. Return the result:

    • After considering all combinations of i, j, k in array arr, we calculated the value of a and b for each triplet and compared them for equality.
    • In our example, let’s say there were no instances where a equaled b. Therefore, the answer ans is 0.

In this example, we did not find any triplets such that a == b. However, we followed the solution approach closely to check for all possible triplets and calculate the XOR for the segments defined by i, j, and k.

Solution Implementation

1from typing import List
2
3class Solution:
4    def countTriplets(self, arr: List[int]) -> int:
5        # Length of the array
6        array_length = len(arr)
7        # Prefix XOR array where prefix[i] represents XOR of all elements from index 0 to i-1
8        prefix = [0] * (array_length + 1)
9        for i in range(array_length):
10            # Compute the prefix XOR values
11            prefix[i + 1] = prefix[i] ^ arr[i]
12
13        # Initialize the count of triplets
14        triplet_count = 0
15        # Iterate over each element considering it as the start of the triplet
16        for i in range(array_length - 1):
17            # Iterate over each element considering it as the middle of the triplet
18            for j in range(i + 1, array_length):
19                # Iterate over each element considering it as the end of the triplet
20                for k in range(j, array_length):
21                    # Calculate XOR of elements from index i to j-1
22                    a = prefix[j] ^ prefix[i]
23                    # Calculate XOR of elements from index j to k
24                    b = prefix[k + 1] ^ prefix[j]
25                    # If XORs are same, increment the count as it satisfies the given condition
26                    if a == b:
27                        triplet_count += 1
28        # Return the total count of triplets found
29        return triplet_count
30
1class Solution {
2    public int countTriplets(int[] arr) {
3        int length = arr.length; // The length of the input array.
4        int[] prefixXor = new int[length + 1]; // Prefix XOR array, with an extra slot to handle 0 case.
5
6        // Construct the prefix XOR array where prefixXor[i] is XOR of all elements from start upto i-1.
7        for (int i = 0; i < length; ++i) {
8            prefixXor[i + 1] = prefixXor[i] ^ arr[i];
9        }
10
11        int count = 0; // The result count for triplets.
12
13        // Iterate through all possible starts i of subarray (arr[i] to arr[k]).
14        for (int i = 0; i < length - 1; ++i) {
15            // Iterate through all possible ends j (where i < j <= k) of subarray starting at arr[i].
16            for (int j = i + 1; j < length; ++j) {
17                // Iterate for all possible ends k of the second subarray, starting from arr[j].
18                for (int k = j; k < length; ++k) {
19                    // XOR of subarray arr[i] to arr[j-1].
20                    int xorA = prefixXor[j] ^ prefixXor[i];
21                    // XOR of subarray arr[j] to arr[k].
22                    int xorB = prefixXor[k + 1] ^ prefixXor[j];
23                  
24                    if (xorA == xorB) { // If the XOR of both subarrays is equal, it's a valid triplet.
25                        count++; // Increment the count of valid triplets.
26                    }
27                }
28            }
29        }
30
31        return count; // Return the final count of triplets.
32    }
33}
34
1class Solution {
2public:
3    int countTriplets(vector<int>& arr) {
4        int n = arr.size(); // Get the size of the array 'arr'
5        vector<int> prefixXOR(n + 1); // Initialize a vector for prefix XOR
6      
7        // Calculate prefix XOR values for the array
8        for (int i = 0; i < n; ++i) {
9            prefixXOR[i + 1] = prefixXOR[i] ^ arr[i];
10        }
11
12        int ans = 0; // Initialize the answer variable to store the count of triplets
13
14        // Triple nested loop to compare all possible combinations of i, j, and k
15        for (int i = 0; i < n - 1; ++i) { // 'i' iterates from 0 to second last element
16            for (int j = i + 1; j < n; ++j) { // 'j' starts from the element next to 'i'
17                for (int k = j; k < n; ++k) { // 'k' starts from 'j' and covers all elements till the end
18
19                    // XOR of elements from i to j-1
20                    int a = prefixXOR[j] ^ prefixXOR[i];
21                    // XOR of elements from j to k
22                    int b = prefixXOR[k + 1] ^ prefixXOR[j];
23
24                    // If the XOR subarray values are the same, increment the answer
25                    if (a == b) {
26                        ++ans;
27                    }
28                }
29            }
30        }
31
32        // Return the final triplet count
33        return ans;
34    }
35};
36
1function countTriplets(arr: number[]): number {
2    const n = arr.length; // Get the size of the array 'arr'
3    let prefixXOR: number[] = new Array(n + 1).fill(0); // Initialize an array for prefix XOR with default values of 0
4  
5    // Calculate prefix XOR values for the array
6    for (let i = 0; i < n; ++i) {
7        prefixXOR[i + 1] = prefixXOR[i] ^ arr[i];
8    }
9
10    let answer = 0; // Initialize the answer variable to store the count of triplets
11
12    // Triple nested loop to compare all possible combinations of i, j, and k
13    for (let i = 0; i < n - 1; ++i) { // 'i' iterates from 0 to the second last element
14        for (let j = i + 1; j < n; ++j) { // 'j' starts from the element next to 'i'
15            for (let k = j; k < n; ++k) { // 'k' starts from 'j' and covers all elements till the end
16
17                // XOR of elements from i to j-1
18                let a = prefixXOR[j] ^ prefixXOR[i];
19                // XOR of elements from j to k
20                let b = prefixXOR[k + 1] ^ prefixXOR[j];
21
22                // If the XOR subarray values are the same, increment the answer
23                if (a === b) {
24                    ++answer;
25                }
26            }
27        }
28    }
29
30    // Return the final triplet count
31    return answer;
32}
33
Not Sure What to Study? Take the 2-min Quiz：

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Time and Space Complexity

Time Complexity

The time complexity of this code can be analyzed through the nested loops within the countTriplets method.

  • There is an initial loop responsible for calculating the prefix XOR array pre, which runs n times, where n is the length of the input array arr. This initial loop has a time complexity of O(n).

  • After that, there are three nested loops indexed by i, j, and k. Loop i runs from 0 to n-2, loop j runs from i+1 to n-1, and loop k runs from j to n-1.

    Therefore, in the worst case, the number of times the innermost loop runs can be computed as: Sum(i=0 to n-2) Sum(j=i+1 to n-1) Sum(k=j to n-1) 1 operations which reduces to O(n^3) because for each outer loop iteration, the innermost loop runs in a decreasing order creating a cubic number of iterations.

Combining these complexities, the total time complexity of the code is dominated by the three nested loops giving us T(n) = O(n) + O(n^3) = O(n^3).

Space Complexity

The space complexity can be observed through the use of extra memory in the code, which is mainly due to the prefix XOR array pre.

  • The array pre has a length n + 1, where n is the length of the input array arr. Thus, the space required for the prefix XOR array is O(n).

  • Besides the array pre, the variables i, j, k, a, and b use a constant amount of space each.

Therefore, considering the extra space used, the total space complexity of the code is S(n) = O(n) because the space used does not grow with respect to the number of loops or operations accomplished, but is directly related to the size of the input n.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫