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

Medium

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] <= 10⁸

Solution:

class Solution {

    /**
     * @param Integer[] $arr
     * @return Integer
     */
    function countTriplets($arr) {
        $ans = 0;
        $xors = [0];
        $prefix = 0;

        foreach ($arr as $key => $a) {
            $prefix ^= $a;
            $xors[] = $prefix;
        }

        for ($j = 1; $j < count($arr); $j++) {
            for ($i = 0; $i < $j; $i++) {
                $xors_i = $xors[$j] ^ $xors[$i];
                for ($k = $j; $k < count($arr); $k++) {
                    $xors_k = $xors[$k + 1] ^ $xors[$j];
                    if ($xors_i == $xors_k) {
                        $ans += 1;
                    }
                }
            }
        }

        return $ans;
    }
}

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub