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

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] <= 108

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