# Number of Unique XOR Triplets II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-unique-xor-triplets-ii)
Canonical: https://scaleengineer.com/dsa/problems/number-of-unique-xor-triplets-ii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array
---
## Problem
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 = 3`

The 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 <= 1500`
* `1 <= nums[i] <= 1500`

# Approaches
## Brute Force Iteration
This is the most straightforward approach. We iterate through all possible triplets of elements from the input array `nums`. For each triplet, we calculate the XOR sum and store it in a hash set to keep track of unique values. The final answer is the size of the hash set.
**Time:** O(n^3), where `n` is the length of `nums`. We have three nested loops, each iterating `n` times. · **Space:** O(U), where `U` is the number of unique XOR triplet values. This is bounded by the maximum possible XOR value, which is less than 2048 given the problem constraints.
**Pros:** Simple to understand and implement.
**Cons:** Very slow due to its cubic time complexity.; Will not pass the time limits for the given constraints (`n <= 1500`).
### Explanation
The brute-force method systematically checks every possible triplet. Since the problem asks for triplets `(i, j, k)` with `i <= j <= k`, this implies choosing three elements from `nums` with replacement. A simpler way to generate the same set of unique XOR values is to iterate `i`, `j`, and `k` independently from `0` to `n-1`. This is because the XOR operation is commutative and associative, so the order of elements does not affect the final value (e.g., `nums[i] ^ nums[j] ^ nums[k]` is the same as `nums[j] ^ nums[i] ^ nums[k]`). A `HashSet` is used to efficiently store only the unique XOR sums encountered.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int countUniqueXorTriplets(int[] nums) {
        Set<Integer> uniqueXorValues = new HashSet<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    uniqueXorValues.add(nums[i] ^ nums[j] ^ nums[k]);
                }
            }
        }
        return uniqueXorValues.size();
    }
}
```
### Algorithm
- Initialize a `HashSet<Integer>` called `uniqueXorValues` to store the unique results.
- Get the length of the array, `n = nums.length`.
- Use three nested loops to iterate through all combinations of indices `(i, j, k)` where `0 <= i < n`, `0 <= j < n`, and `0 <= k < n`.
- Inside the innermost loop, calculate `xorSum = nums[i] ^ nums[j] ^ nums[k]`.
- Add `xorSum` to the `uniqueXorValues` set. The set automatically handles duplicates.
- After the loops complete, the number of unique XOR triplet values is the size of the set. Return `uniqueXorValues.size()`.

## Optimized Two-Step XOR Calculation
This approach improves upon the brute-force method by breaking down the calculation. Instead of a three-level nested loop, we can first compute all possible XOR sums of pairs of elements (`nums[i] ^ nums[j]`) and store these unique pairwise XOR sums in a set. Then, we iterate through this set of pairwise sums and XOR each of them with every element `nums[k]` from the original array. This reduces the complexity from cubic to quadratic.
**Time:** O(n^2 + |P| * n), where `n` is the length of `nums` and `|P|` is the number of unique pairwise XOR sums. Since `|P|` is bounded by a constant related to the maximum value in `nums` (let's call it `V_max`), the complexity is effectively O(n^2 + V_max * n), which is dominated by O(n^2) for the given constraints. · **Space:** O(V_max), where `V_max` is the maximum possible XOR value (approx. 2048). This space is used for storing the `pairXors` and `tripletXors` sets.
**Pros:** Significantly faster than the brute-force approach.; Efficient enough to pass the given constraints.
**Cons:** While much better than O(n^3), it might still be too slow if `n` were significantly larger.
### Explanation
The core idea is to use the associative property of XOR: `a ^ b ^ c = (a ^ b) ^ c`. By pre-calculating all possible values of `a ^ b`, we can reduce the number of operations.

First, we generate all unique values of `nums[i] ^ nums[j]` and store them in a set, `pairXors`. This takes O(n^2) time. The size of this set is bounded by the maximum possible XOR value of two numbers in `nums` (less than 2048).

Next, we iterate through each pre-calculated pairwise XOR sum `p` and XOR it with every number `num` in the original `nums` array. The results are stored in a final set, `tripletXors`, to count the unique values. This step takes O(|`pairXors`| * n) time.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int countUniqueXorTriplets(int[] nums) {
        Set<Integer> pairXors = new HashSet<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                pairXors.add(nums[i] ^ nums[j]);
            }
        }

        Set<Integer> tripletXors = new HashSet<>();
        for (int pXor : pairXors) {
            for (int num : nums) {
                tripletXors.add(pXor ^ num);
            }
        }
        return tripletXors.size();
    }
}
```
### Algorithm
- Initialize a `HashSet<Integer>` called `pairXors` to store unique XOR values of pairs.
- Iterate through all pairs of elements `(nums[i], nums[j])` from the input array using two nested loops.
- For each pair, calculate `nums[i] ^ nums[j]` and add the result to `pairXors`.
- Initialize another `HashSet<Integer>` called `tripletXors` for the final unique triplet XORs.
- Iterate through each value `p` in `pairXors`.
- For each `p`, iterate through all elements `num` in `nums`.
- Calculate `p ^ num` and add it to `tripletXors`.
- The final answer is the size of `tripletXors`.

## Fast Walsh-Hadamard Transform (FWHT)
This is the most advanced and efficient approach. The problem of finding all possible values of `a ^ b ^ c` can be modeled as a threefold XOR convolution of a set with itself. The Fast Walsh-Hadamard Transform (FWHT) is an algorithm that can compute XOR convolution in O(N log N) time, which is significantly faster than the naive O(N^2) method.
**Time:** O(V log V), where `V` is the power of 2 that bounds the maximum possible XOR value. Given the constraints, `V=2048`, so the complexity is very low and constant with respect to `n`. · **Space:** O(V), where `V` is the power of 2 that bounds the maximum possible XOR value (2048 in this case). This space is for the frequency/transform array.
**Pros:** Extremely efficient, with a quasi-linear time complexity.; It is the asymptotically fastest known method for this type of problem.
**Cons:** The concept of FWHT is more complex and less intuitive than other approaches.; Implementation requires careful handling of details like data types (using `long` to avoid overflow) and the transform logic.
### Explanation
We can represent the set of numbers in `nums` as a frequency array `A`, where `A[i]` is 1 if `i` is present in `nums`, and 0 otherwise. Finding all possible values of `a ^ b ^ c` is equivalent to finding the support (the set of indices with non-zero values) of the threefold XOR convolution `A * A * A`.

The FWHT provides a powerful tool for this. Based on the convolution theorem, `FWHT(A * B) = FWHT(A) .* FWHT(B)` (where `.*` denotes element-wise product). We can leverage this to compute the convolution efficiently.

The process involves transforming the frequency array `A` into the FWHT domain, performing element-wise cubing (for the threefold convolution), and then transforming it back with the inverse FWHT. The final array's non-zero entries give us the unique XOR triplet values.

```java
class Solution {
    public int countUniqueXorTriplets(int[] nums) {
        // V must be a power of 2 and >= max possible XOR sum.
        // Max value is 1500, so max XOR sum of 3 numbers is < 2048.
        int V = 2048;

        long[] p = new long[V];
        for (int num : nums) {
            p[num] = 1;
        }

        // Forward FWHT
        fwht(p, false);

        // Element-wise cube in the transform domain
        for (int i = 0; i < V; i++) {
            p[i] = p[i] * p[i] * p[i];
        }

        // Inverse FWHT
        fwht(p, true);

        int count = 0;
        for (int i = 0; i < V; i++) {
            if (p[i] > 0) {
                count++;
            }
        }
        return count;
    }

    // In-place Fast Walsh-Hadamard Transform for XOR convolution
    private void fwht(long[] a, boolean inverse) {
        int n = a.length;
        for (int len = 1; len < n; len <<= 1) {
            for (int i = 0; i < n; i += 2 * len) {
                for (int j = 0; j < len; j++) {
                    long u = a[i + j];
                    long v = a[i + len + j];
                    a[i + j] = u + v;
                    a[i + len + j] = u - v;
                }
            }
        }

        if (inverse) {
            for (int i = 0; i < n; i++) {
                a[i] = a[i] / n;
            }
        }
    }
}
```
### Algorithm
- Determine the size `V` for our arrays. It must be a power of 2 large enough to hold any possible XOR sum. Given `max(nums[i]) <= 1500`, `V = 2048` is sufficient.
- Create a frequency array `P` of size `V` (using `long` to prevent overflow). For each `num` in `nums`, set `P[num] = 1`.
- Apply the Fast Walsh-Hadamard Transform (FWHT) to `P`. Let's call the result `hat_P`.
- Create a new array `hat_P3` by cubing each element of `hat_P`: `hat_P3[i] = hat_P[i] * hat_P[i] * hat_P[i]`. This corresponds to the transform of the threefold convolution.
- Apply the inverse FWHT to `hat_P3` to get the result array `P3`. The value `P3[k]` will represent the number of ways the value `k` can be formed by XORing three numbers from `nums`.
- Count the number of indices `k` for which `P3[k]` is non-zero. This count is the number of unique XOR triplet values.