Watch 3 video solutions for Number of Unique XOR Triplets II, a medium level problem involving Array, Math, Bit Manipulation. This walkthrough by CodeWithMe21 has 494 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums.
A XOR triplet is defined as the XOR of three elements nums[i] XOR nums[j] XOR nums[k] where i <= j <= k.
Return the number of unique XOR triplet values from all possible triplets (i, j, k).
Example 1:
Input: nums = [1,3]
Output: 2
Explanation:
The possible XOR triplet values are:
(0, 0, 0) → 1 XOR 1 XOR 1 = 1(0, 0, 1) → 1 XOR 1 XOR 3 = 3(0, 1, 1) → 1 XOR 3 XOR 3 = 1(1, 1, 1) → 3 XOR 3 XOR 3 = 3The unique XOR values are {1, 3}. Thus, the output is 2.
Example 2:
Input: nums = [6,7,8,9]
Output: 4
Explanation:
The possible XOR triplet values are {6, 7, 8, 9}. Thus, the output is 4.
Constraints:
1 <= nums.length <= 15001 <= nums[i] <= 1500Problem Overview: You are given an array and must compute how many distinct XOR values can be formed using triplets of indices. Each triplet contributes a ^ b ^ c. The goal is not the number of triplets but the number of unique XOR results they produce.
Approach 1: Brute Force Triplet Enumeration (O(n^3) time, O(k) space)
The most direct solution iterates over every possible triplet (i, j, k) with three nested loops. For each combination, compute nums[i] ^ nums[j] ^ nums[k] and store the result in a hash set to keep only distinct values. After processing all triplets, the size of the set gives the answer. This approach is easy to reason about and confirms correctness, but the O(n^3) runtime becomes impractical once the array grows beyond a few hundred elements.
Approach 2: Pair XOR Enumeration with Set Deduplication (O(n^2) time, O(n^2) space)
A more efficient strategy reduces one level of enumeration. First compute XOR values for all index pairs and store them in a structure such as a set or list. Then combine each pair XOR with every element to produce candidate triplet XOR values. Because (a ^ b) ^ c = a ^ b ^ c, this transformation preserves the result while avoiding the explicit third nested loop over indices. Store the generated values in a set to ensure uniqueness. The algorithm performs roughly O(n^2) pair computations and another O(n^2) combinations, which is far more manageable than cubic enumeration.
The key insight is the associativity of XOR. Grouping two numbers first lets you reuse pair results across multiple triplets. Hash sets handle deduplication efficiently, making the solution practical for medium-sized arrays.
Conceptually this problem sits at the intersection of array processing, bit manipulation, and some light mathematical reasoning. Recognizing XOR properties—associativity, commutativity, and self-cancellation—is what enables the optimization.
Recommended for interviews: Start with the brute force explanation to demonstrate understanding of the problem space. Then move to the pair‑XOR enumeration approach. Interviewers expect candidates to notice that XOR can be regrouped, allowing a reduction from O(n^3) to about O(n^2) while still using simple data structures like sets.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Triplet Enumeration | O(n^3) | O(k) for unique XOR set | Small arrays or when validating correctness during implementation |
| Pair XOR Enumeration + Hash Set | O(n^2) | O(n^2) | General case; significantly faster by leveraging XOR associativity |
| Pair XOR with On‑the‑fly Deduplication | O(n^2) | O(k) | When memory is tighter and pair results are combined immediately |