LeetCode Entry

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

30.05.2024 medium 2024 kotlin rust

Number (i,j,k) where xor arr[i..j] = xor arr[j..k] manipulation

1442. Count Triplets That Can Form Two Arrays of Equal XOR medium blog post substack youtube 2024-05-30_07-53.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/622

Problem TLDR

Number (i,j,k) where xor arr[i..j] = xor arr[j..k] #medium #bit_manipulation

Intuition

Start with the brute-force solution, it will be accepted.

                for (j in i + 1..k)
                    a = a ^ arr[j]
                    b = ikXor ^ a
                    if (a == b) res++

Some optimizations:

  • we have precomputed total xor between i..k and now if a = xor [i..j - 1] then b = xor [i..k] ^ a.

Let’s inline a and b in the if (a == b) equation:

if (a ^ arr[j] == ikXor ^ (a ^ arr[j])) ...

We can safely remove ^ a ^ arr[j] from the left and the right parts, leaving it like if (0 == ikXor). As this now independent of j, we can just collapse the third loop into ` if (0 == ikXor) res += k - i`.

(There is one more optimization possible: store xors prefixes count in a HashMap, this will reduce the time to O(n))

Approach

Using sumOf and .map().sum() helps to reduce some lines of code.

Complexity

  • Time complexity: \(O(n^2)\)

  • Space complexity: \(O(1)\)

Code


    fun countTriplets(arr: IntArray): Int =
        arr.indices.sumOf { i ->
            var ikXor = 0
            (i..<arr.size).sumOf { k ->
                ikXor = ikXor xor arr[k]
                if (0 == ikXor) k - i else 0
            }
        }



    pub fn count_triplets(arr: Vec<i32>) -> i32 {
        (0..arr.len()).map(|i| {
            let mut ik_xor = 0;
            (i..arr.len()).map(|k| {
                ik_xor ^= arr[k];
                if ik_xor == 0 { k - i } else { 0 }
            }).sum::<usize>()
        }).sum::<usize>() as _
    }