# Number of Unique XOR Triplets I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-unique-xor-triplets-i)
Canonical: https://scaleengineer.com/dsa/problems/number-of-unique-xor-triplets-i
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
---
## Problem
You are given an integer array `nums` of length `n`, where `nums` is a **permutation** of the numbers in the range `[1, n]`.

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,2\]

**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 2 = 2`
* `(0, 1, 1) → 1 XOR 2 XOR 2 = 1`
* `(1, 1, 1) → 2 XOR 2 XOR 2 = 2`

The unique XOR values are `{1, 2}`, so the output is 2.

**Example 2:**

**Input:** nums = \[3,1,2\]

**Output:** 4

**Explanation:**

The possible XOR triplet values include:

* `(0, 0, 0) → 3 XOR 3 XOR 3 = 3`
* `(0, 0, 1) → 3 XOR 3 XOR 1 = 1`
* `(0, 0, 2) → 3 XOR 3 XOR 2 = 2`
* `(0, 1, 2) → 3 XOR 1 XOR 2 = 0`

The unique XOR values are `{0, 1, 2, 3}`, so the output is 4.

**Constraints:**

* `1 <= n == nums.length <= 105`
* `1 <= nums[i] <= n`
* `nums` is a permutation of integers from `1` to `n`.

# Approaches
## Brute-Force Enumeration
The most straightforward approach is to simulate the process described in the problem. We can generate every possible triplet `(i, j, k)` that satisfies the condition `i <= j <= k`, calculate the XOR sum `nums[i] XOR nums[j] XOR nums[k]`, and store these results in a hash set to keep track of the unique values. The final answer is the size of this set.
**Time:** O(n^3), where n is the length of the `nums` array. The three nested loops lead to a cubic time complexity, which is too slow for the given constraints. · **Space:** O(M), where M is the number of unique XOR triplet values. The maximum possible XOR value is bounded by the next power of 2 greater than `n`, so in the worst case, the space is proportional to `n` (e.g., O(2n)).
**Pros:** Simple to understand and implement.; Correct for small input sizes.
**Cons:** Extremely inefficient with a time complexity of O(n^3).; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints (n <= 10^5).
### Explanation
This method involves a brute-force enumeration of all valid triplets. We use three nested loops. The outer loop runs from `i = 0` to `n-1`, the middle loop from `j = i` to `n-1`, and the inner loop from `k = j` to `n-1`. This structure ensures that we only consider triplets `(i, j, k)` where `i <= j <= k`.

For each triplet, we compute the XOR sum of the corresponding elements from the `nums` array. To count the number of unique results, we use a `HashSet`. Each computed XOR value is added to the set. If the value is already present, the set remains unchanged. Finally, the total number of unique values is simply the size of the hash set.

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

class Solution {
    public int countUniqueXorTriplets(int[] nums) {
        int n = nums.length;
        Set<Integer> uniqueValues = new HashSet<>();

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                for (int k = j; k < n; k++) {
                    uniqueValues.add(nums[i] ^ nums[j] ^ nums[k]);
                }
            }
        }

        return uniqueValues.size();
    }
}
```
### Algorithm
1. Initialize an empty `HashSet` called `uniqueValues` to store the unique XOR triplet results.
2. Get the length of the input array `nums`, let it be `n`.
3. Use three nested loops to iterate through all possible triplets of indices `(i, j, k)` such that `0 <= i <= j <= k < n`.
4. In the innermost loop, calculate the XOR sum: `value = nums[i] ^ nums[j] ^ nums[k]`.
5. Add the calculated `value` to the `uniqueValues` set. The set automatically handles duplicates.
6. After the loops complete, the number of unique XOR triplets is the size of the `uniqueValues` set. Return this size.

## Fast Walsh-Hadamard Transform (FWHT)
A more optimized approach uses polynomial multiplication via the Fast Walsh-Hadamard Transform (FWHT) to solve the XOR sumset problem. First, we observe that because `nums` is a permutation of `{1, ..., n}`, the problem is equivalent to finding the size of the set `V = {1, ..., n} igcup {a^b^c | a,b,c 	ext{ are distinct elements from } {1, ..., n}}`. This set can be expressed as a sumset `P_2 igoplus S`, where `S = {1, ..., n}` and `P_2 = {a^b | a,b 	ext{ are distinct in } S}`. FWHT allows us to compute the characteristic polynomial of this sumset efficiently.
**Time:** O(N log N), where N is the smallest power of 2 greater than `2n`. This is dominated by the FWHT computations. For `n=10^5`, this is efficient enough. · **Space:** O(N), where N is the smallest power of 2 greater than `2n`. Since `n <= 10^5`, `N` can be up to `262144`, so the space is O(n).
**Pros:** Significantly more efficient than the brute-force approach.; Can solve the problem within the time limits for the given constraints.
**Cons:** Complex to implement, requiring knowledge of advanced algorithms like FWHT.; The constant factors in the complexity are relatively large.; Still not the most optimal solution.
### Explanation
This approach transforms the combinatorial problem into an algebraic one using polynomial convolution.

1.  **Problem Reformulation**: The set of all possible XOR values is `S igcup P_3`, where `S = {1, ..., n}` and `P_3 = {a^b^c | a,b,c 	ext{ distinct in } S}`. This can be shown to be equivalent to `P_2 igoplus S = {p^c | p 	ext{ in } P_2, c 	ext{ in } S}`, where `P_2 = {a^b | a,b 	ext{ distinct in } S}`.

2.  **XOR Convolution**: We can find the elements of a sumset `A igoplus B` by computing the XOR convolution of their characteristic polynomials. The FWHT algorithm computes this convolution in `O(N log N)` time, where `N` is the size of the polynomial domain (a power of two large enough to hold all values).

3.  **Algorithm Steps**:
    a.  Choose `N` to be the smallest power of 2 greater than `2n`.
    b.  Create a polynomial `polyS` for `S = {1, ..., n}`.
    c.  Use FWHT to compute `polyP2` from `polyS` by first computing the convolution `polyS * polyS`.
    d.  Use FWHT again to compute the convolution `polyP2 * polyS` to get the final result polynomial.
    e.  Count the number of non-zero entries in the result polynomial.

```java
import java.util.Arrays;

class Solution {
    // This is a conceptual implementation. For competitive programming,
    // a more optimized FWHT implementation would be used.
    public int countUniqueXorTriplets(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;

        int N = 1;
        while (N <= 2 * n) {
            N <<= 1;
        }

        long[] polyS = new long[N];
        for (int i = 1; i <= n; i++) {
            polyS[i] = 1;
        }

        long[] h_S = Arrays.copyOf(polyS, N);
        fwht(h_S, false);

        long[] h_S_conv_S = new long[N];
        for (int i = 0; i < N; i++) {
            h_S_conv_S[i] = h_S[i] * h_S[i];
        }
        fwht(h_S_conv_S, true);

        long[] polyP2 = new long[N];
        for (int i = 1; i < N; i++) {
            if (h_S_conv_S[i] > 0) {
                polyP2[i] = 1;
            }
        }

        long[] h_P2 = Arrays.copyOf(polyP2, N);
        fwht(h_P2, false);

        long[] h_Q = new long[N];
        for (int i = 0; i < N; i++) {
            h_Q[i] = h_P2[i] * h_S[i];
        }
        fwht(h_Q, true);

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

    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] /= n;
            }
        }
    }
}
```
### Algorithm
1. **Identify the set of possible values:** Realize that the set of unique XOR values is the union of `{1, ..., n}` and `{a^b^c | a,b,c 	ext{ are distinct in } {1,...,n}}`. This can be shown to be equivalent to the set `{p^c | p 	ext{ in } P_2, c 	ext{ in } S}`, where `S = {1,...,n}` and `P_2 = {a^b | a,b 	ext{ distinct in } S}`.
2. **Represent sets as polynomials:** Create boolean arrays (polynomials) `polyS` and `polyP2` of size `N` (smallest power of 2 > 2n) to represent the characteristic functions of the sets `S` and `P_2`.
3. **Compute `polyP2` using FWHT:** The set `P_2` is `(S igoplus S) \setminus \{0\}`. Its polynomial can be computed via XOR convolution of `polyS` with itself: `poly(S igoplus S) = IFWHT(FWHT(polyS) igodot FWHT(polyS))`. Set the coefficient for 0 to be false to get `polyP2`.
4. **Compute the final set polynomial:** The final set of values is `P_2 igoplus S`. Its polynomial is found by another XOR convolution: `poly(Result) = IFWHT(FWHT(polyP2) igodot FWHT(polyS))`. 
5. **Count unique values:** The number of unique values is the number of non-zero coefficients in the final polynomial `poly(Result)`.

## Mathematical Observation
The most efficient solution comes from a mathematical observation about the structure of XOR sums over the set of integers `{1, ..., n}`. By analyzing the problem for small values of `n`, a pattern emerges. This pattern can be proven to hold for all `n`, leading to a constant-time solution.
**Time:** O(1), as the solution involves a few comparisons and bitwise operations that do not depend on `n`. · **Space:** O(1), as no extra space proportional to the input size is needed.
**Pros:** Extremely efficient with O(1) time complexity.; Minimal space usage.; Very simple to implement once the mathematical property is known.
**Cons:** Relies on a non-trivial mathematical property that may not be immediately obvious.; The correctness depends on number-theoretic results about XOR sums.
### Explanation
The key insight is that since `nums` is a permutation of `{1, ..., n}`, the problem is independent of the order of elements in `nums` and only depends on `n`. The set of unique values is `{1, ..., n} igcup {a^b^c | a,b,c 	ext{ are distinct in } {1,...,n}}`.

By analyzing small cases:
-   **n=1**: `nums=[1]`. Values: `{1}`. Size: 1.
-   **n=2**: `nums` is perm of `{1,2}`. Values: `{1,2}`. Size: 2.
-   **n=3**: `nums` is perm of `{1,2,3}`. Values: `{1,2,3}` and `1^2^3=0`. Total: `{0,1,2,3}`. Size: 4.
-   **n=4**: `nums` is perm of `{1,2,3,4}`. Values: `{1,2,3,4}` and `{1^2^3=0, 1^2^4=7, 1^3^4=6, 2^3^4=5}`. Total: `{0,1,2,3,4,5,6,7}`. Size: 8.

For `n >= 3`, it can be shown that the set of all possible XOR triplet values forms a complete range of numbers from `0` to `p-1`, where `p` is the smallest power of 2 strictly greater than `n`. The size of this set is `p`.

This value `p` can be found efficiently. For a given `n`, `p` is `2^k` where `k` is the smallest integer such that `2^k > n`. This is equivalent to finding the next power of two after `n`.

For example, if `n=5`, the next power of two is 8. If `n=8`, the next power of two is 16.

This leads to a very simple and fast implementation.

```java
class Solution {
    public int countUniqueXorTriplets(int[] nums) {
        int n = nums.length;

        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }

        // For n >= 3, the result is the smallest power of 2 strictly greater than n.
        // This can be found using bit manipulation.
        // Integer.highestOneBit(n) finds the largest power of 2 less than or equal to n.
        // If n is a power of 2, say n = 8, highestOneBit(8) is 8. We need 16. So 8 << 1.
        // If n is not a power of 2, say n = 7, highestOneBit(7) is 4. We need 8. So 4 << 1.
        // This logic holds for n >= 1, but we've handled n=1,2 separately for clarity.
        // Let's re-check the formula for n=3: highestOneBit(3) is 2. 2 << 1 = 4. Correct.
        return Integer.highestOneBit(n) << 1;
    }
}
```
### Algorithm
1. Handle the base cases for small `n`.
   - If `n = 1`, the only possible triplet is `(1,1,1)` giving `1^1^1=1`. The result is 1.
   - If `n = 2`, the unique values are `{1, 2}`. The result is 2.
2. For `n >= 3`, observe the pattern of the unique values.
   - `n=3`: `{1,2,3}`. `1^2^3=0`. Unique values are `{0,1,2,3}`. Size 4.
   - `n=4`: `{1,2,3,4}`. Triplets generate `{0,5,6,7}`. Unique values are `{0,1,2,3,4,5,6,7}`. Size 8.
3. Generalize the pattern: For `n >= 3`, the set of unique XOR values is `{0, 1, ..., p-1}`, where `p` is the smallest power of 2 that is strictly greater than `n`.
4. The size of this set is `p`. This can be calculated efficiently using bit manipulation.
5. Implement the logic: check for `n=1` and `n=2`, otherwise calculate and return `p`.