_1442. Count Triplets That Can Form Two Arrays of Equal XOR.md

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

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 08, 2024

Last updated : July 04, 2024

---

Related Topics : Array, Hash Table, Math, Bit Manipulation, Prefix Sum

Acceptance Rate : 84.93 %

---

    Notes
    Negation of XOR is Biconditional 
    i.e. p <-> q
    (p -> q) and (q -> p)
    (!p or q) and (!q or p)
    (!p and !q) or (p and q)
    p == q


    1^0 --> 1 -->  --> 1^0 --> 1
    1^1 --> 0 -->  --> 0^1 --> 1
    0^0 --> 0 -->  --> 0^0 --> 0
    0^1 --> 1 -->  --> 1^1 --> 0

    XORing by the same value again reverses the result!

    Since 0 <= i < j <= k < arr.len --> k-i+1 >= 2

    If two arrays XOR together to get 0, then the two 
    individual sections should have an XOR 
    that equal each other.

    That is, XOR(arr1) == XOR(arr2) so that XOR(arr1, arr2) == 0

---

Solutions

• m1442 Daily.py

Python

m1442 Daily.py

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        counter = 0
        for k in range(len(arr) - 1, 0, -1) :
            current = arr[k]
            for i in range(k - 1, -1, -1) :
                current ^= arr[i]
                if (current == 0) :
                    # counter += 1
                    counter += k - i
        return counter