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

Intuition

To find the number of triplets (i, j, k) where a == b given the conditions, we can use the prefix XOR technique. The key observation is that if the XOR from i to k is zero (pref[i] == pref[k+1]), it implies there exists at least one j such that the XOR from i to j-1 is equal to the XOR from j to k.

Approach

1. Prefix XOR Array: - Create a prefix XOR array pref where pref[i] is the XOR of all elements from the start of the array up to the i-1 index. - Initialize pref[0] to 0. - Calculate pref[i] for each i from 1 to n as pref[i] = pref[i - 1] ^ arr[i - 1].
2. Find Triplets: - Use nested loops to iterate over possible values of i and k. - For each pair (i, k), check if pref[i] == pref[k + 1]. - If the condition is met, increment the result by k - i, as there are k - i valid values for j between i and k.
3. Return the Result: - Return the total count of valid triplets.

Complexity

• Time complexity: \(O(n^2)\) - The nested loops to check all pairs (i, k) take \(O(n^2)\) time.
• Space complexity: \(O(n)\) - The prefix XOR array pref requires \(O(n)\) space.

Code

C

int countTriplets(int* arr, int n) {
    int pref[n + 1];
    pref[0] = 0;
    for (int i = 1; i <= n; i++) {
        pref[i] = pref[i - 1] ^ arr[i - 1];
    }

    int res = 0;
    for (int i = 0; i < n; i++) {
        for (int k = i + 1; k < n; k++) {
            if (pref[i] == pref[k + 1]) {
                res += k - i;
            }
        }
    }

    return res;
}

C++

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

        int res = 0;
        for (int i = 0; i < n; ++i) {
            for (int k = i + 1; k < n; ++k) {
                if (pref[i] == pref[k + 1]) {
                    res += k - i;
                }
            }
        }

        return res;
    }
};

Python

class Solution:
    def countTriplets(self, arr):
        n = len(arr)
        pref = [0] * (n + 1)
        for i in range(1, n + 1):
            pref[i] = pref[i - 1] ^ arr[i - 1]

        res = 0
        for i in range(n):
            for k in range(i + 1, n):
                if pref[i] == pref[k + 1]:
                    res += k - i

        return res

Java

class Solution {
    public int countTriplets(int[] arr) {
        int n = arr.length;
        int[] pref = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            pref[i] = pref[i - 1] ^ arr[i - 1];
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int k = i + 1; k < n; k++) {
                if (pref[i] == pref[k + 1]) {
                    res += k - i;
                }
            }
        }

        return res;
    }
}

JavaScript

/**
 * @param {number[]} arr
 * @return {number}
 */
var countTriplets = function (arr) {
  var n = arr.length;
  var pref = new Uint32Array(n + 1);
  for (var i = 1; i <= n; i++) pref[i] = pref[i - 1] ^ arr[i - 1];
  var res = 0;
  for (var i = 0; i < n; i++) {
    for (var k = i + 1; k < n; k++) {
      if (pref[i] === pref[k + 1]) res += k - i;
    }
  }
  return res;
};

TypeScript

function countTriplets(arr: number[]): number {
  var n = arr.length;
  var pref = new Uint32Array(n + 1);
  for (var i = 1; i <= n; i++) pref[i] = pref[i - 1] ^ arr[i - 1];
  var res = 0;
  for (var i = 0; i < n; i++) {
    for (var k = i + 1; k < n; k++) {
      if (pref[i] === pref[k + 1]) res += k - i;
    }
  }
  return res;
}

Go

func countTriplets(arr []int) int {
	n := len(arr)
	pref := make([]int, n+1)
	for i := 1; i <= n; i++ {
		pref[i] = pref[i-1] ^ arr[i-1]
	}
	res := 0
	for i := 0; i < n; i++ {
		for k := i + 1; k < n; k++ {
			if pref[i] == pref[k+1] {
				res += k - i
			}
		}
	}
	return res
}

C#

public class Solution {
    public int CountTriplets(int[] arr) {
        int n = arr.Length;
        int[] pref = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            pref[i] = pref[i - 1] ^ arr[i - 1];
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int k = i + 1; k < n; k++) {
                if (pref[i] == pref[k + 1]) {
                    res += k - i;
                }
            }
        }

        return res;
    }
}