Number of Unique XOR Triplets II

Number of Unique XOR Triplets II

What is this problem about?

The Number of Unique XOR Triplets II extends the first problem to an arbitrary array (not necessarily 1..n). Count the distinct XOR values achievable by any triplet of elements (with repetition allowed if indices allow). This harder variant requires actually computing reachable XOR values, often using a meet-in-the-middle or prefix XOR set approach.

Why is this asked in interviews?

Meesho asks this to test whether candidates can adapt from the formulaic Part I to a computational approach for general arrays. The array, math, enumeration, and bit manipulation interview pattern is the core, and the meet-in-the-middle technique reduces O(n³) to O(n² log n).

Algorithmic pattern used

Set of all pairwise XOR values. First compute all distinct pairwise XOR values: for each pair (i,j), compute arr[i] ^ arr[j] and store in a set pairs. Then for each unique pair XOR value p and each element arr[k], compute p ^ arr[k] and add to a result set. Return the size of the result set. This is O(n²) for pairs + O(n² * n_unique_pairs) for triplets — optimized by using sets.

Example explanation

arr=[2,1,3]. Distinct elements. Pair XORs: 2^1=3, 2^3=1, 1^3=2, 2^2=0, 1^1=0, 3^3=0. Unique pair XORs: {0,1,2,3}. Triplet XORs: 0^2=2, 0^1=1, 0^3=3, 1^2=3, 1^1=0, 1^3=2, 2^2=0, 2^1=3, 2^3=1, 3^2=1, 3^1=2, 3^3=0. Union: {0,1,2,3}. Count = 4.

Common mistakes candidates make

• O(n³) brute force (too slow for large arrays).
• Not using a set for deduplication.
• Forgetting that XOR with oneself (i=j=k) should be included (problem allows i≤j≤k with repetition).
• Confusing this with Part I's mathematical formula (general arrays don't have the same closed form).

Interview preparation tip

When exact enumeration is needed for XOR triplets on general arrays, the meet-in-the-middle approach splits the work: compute all pair XORs first, then extend to triplets. This reduces O(n³) sets to O(n²) pairs followed by O(n²) extensions. Practice XOR enumeration using set-based deduplication — it's efficient for small n and demonstrates understanding of XOR's mathematical properties.