Difficulty: 🟡 Medium
Topics: Array, Math, Bit Manipulation, Enumeration

Solution

LeetCode 3514 - Number of Unique XOR Triplets II

Problem Understanding

We are given an integer array nums, and we must consider every triplet of indices (i, j, k) such that i <= j <= k.

For each valid triplet, we compute:

$$nums[i] \oplus nums[j] \oplus nums[k]$$

where ⊕ denotes the bitwise XOR operation.

The goal is not to count triplets. Instead, we must determine how many different XOR values can be produced by all possible triplets.

A very important detail is that the condition is i <= j <= k, not i < j < k. This means the same index may appear multiple times. For example, (0,0,0) is a valid triplet. Therefore, if a value exists in the array, it can be selected multiple times in a triplet.

The constraints are the key to solving the problem efficiently:

1 <= nums.length <= 1500
1 <= nums[i] <= 1500

Since every value is at most 1500, all numbers fit within 11 bits because:

$$1500 < 2^{11} = 2048$$

Therefore, every XOR result must lie in the range [0, 2047].

This bounded XOR space is the critical observation. Even though there may be millions or billions of possible triplets conceptually, there are only 2048 possible XOR values.

Several edge cases are worth noticing immediately:

Arrays of length one still produce valid triplets because (0,0,0) is allowed.
Duplicate values do not create new XOR possibilities beyond what the value itself already contributes.
The answer can never exceed 2048 because there are only 2048 possible XOR outcomes.

Problem Understanding

The problem asks us to compute the number of unique XOR triplet values from an array of integers nums. A XOR triplet is defined as nums[i] XOR nums[j] XOR nums[k] where the indices satisfy i <= j <= k. The input array nums contains between 1 and 1500 integers, each ranging from 1 to 1500. The output is a single integer, representing the number of distinct results from evaluating XOR over all possible triplets.

In simpler terms, we are asked to enumerate every combination of three elements from the array (allowing repetitions of the same index) and apply the XOR operation. From all results, we count how many unique values exist. The constraints allow arrays up to length 1500, meaning a naive triple-nested loop would perform $O(n^3)$ operations, which is approximately 3.3 billion operations at the maximum size - too slow for practical execution.

Important edge cases include arrays with:

Only one element, where all triplets are identical.
All elements identical, which produces a single XOR value.
Distinct elements in small arrays, to verify correct enumeration of triplets.

Approaches

Brute Force

The most direct approach is to enumerate every valid triplet (i, j, k).

For each triplet:

Compute nums[i] XOR nums[j] XOR nums[k].
Insert the result into a hash set.
Return the size of the set.

This is correct because it explicitly generates every possible triplet and records every produced XOR value.

Unfortunately, the complexity is:

$$O(n^3)$$

With n = 1500, this would require more than three billion triplets, which is completely infeasible.

Key Insight

Because indices may repeat, every triplet result is simply:

$$a \oplus b \oplus c$$

where a, b, and c are values that appear somewhere in the array.

The actual indices no longer matter. Only the set of available values matters.

Next, observe that all values are at most 1500, so every XOR result lies in the range [0, 2047].

Instead of reasoning about triplets directly, we can work in the XOR value space:

Compute every possible value of a XOR b.
Store these results in a boolean array of size 2048.
For every reachable pair XOR value and every array value c, mark:

$$(a \oplus b) \oplus c$$ 4. Count how many XOR values become reachable.

Since the XOR space contains only 2048 values, this approach is extremely efficient.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(2048)	Enumerates all triplets
Optimal	O(m² + 2048·m)	O(2048)	Uses bounded XOR state space, where `m` is the number of distinct values

Here, m is the number of distinct values in the array and m ≤ 1500.

Algorithm Walkthrough

Convert the array into a set of distinct values.

Duplicate values are irrelevant because a value either exists or does not exist. Since indices may be reused, having multiple copies of the same value does not create any new XOR possibilities. 2. Create a boolean array pair_xor of size 2048.

pair_xor[x] will indicate whether some pair of values produces XOR result x. 3. Enumerate every pair (a, b) from the distinct values.

For each pair, compute:

$$a \oplus b$$

and mark the corresponding position in pair_xor. 4. Create another boolean array triple_xor of size 2048.

This array will track all reachable triplet XOR values. 5. For every reachable pair XOR value p and every distinct value c, compute:

$$p \oplus c$$

and mark it in triple_xor. 6. Count how many entries in triple_xor are True.

That count is exactly the number of unique XOR triplet values.

Why it works

Every valid triplet result has the form:

$$a \oplus b \oplus c$$

for some values appearing in the array.

The algorithm first enumerates all possible values of a XOR b, then combines each of them with every possible c. Therefore every achievable triplet XOR value is generated.

Conversely, every value generated by the algorithm corresponds to some choice of three array values, so it is a valid triplet XOR result.

Thus the set produced by the algorithm is exactly the set of all unique XOR triplet values. The brute-force approach is straightforward: enumerate all triplets (i, j, k) where i <= j <= k and compute nums[i] XOR nums[j] XOR nums[k]. Store all results in a set to eliminate duplicates, then return the size of the set. This approach is correct because it exhaustively enumerates all valid triplets, guaranteeing that no unique XOR value is missed.

However, the brute-force approach requires $O(n^3)$ time because there are $\binom{n+2}{3}$ triplets in total. For the upper bound of $n = 1500$, this is prohibitively slow. Memory-wise, the set stores up to $n^3$ values in the worst case, though practically the number of unique XOR results is smaller.

Optimal

The key insight is that XOR is associative and commutative, which allows us to reduce the complexity by iterating over pairs (i, j) and computing partial XORs. Specifically, consider:

$$\text{triplet_xor} = nums[i] \oplus nums[j] \oplus nums[k] = (nums[i] \oplus nums[j]) \oplus nums[k]$$

If we precompute all possible XORs of two elements (i <= j) and store them in a set, we can then XOR each value with each element nums[k] (for k >= j) to produce all triplet results. With careful indexing, this reduces the number of operations from $O(n^3)$ to $O(n^2)$ in practice.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^3)	O(n^3)	Enumerates all triplets explicitly
Optimal	O(n^2)	O(n^2)	Uses pair XORs and extends them with the third element

Algorithm Walkthrough

Initialize an empty set triplet_xors to store unique XOR values.
Iterate over the first index i from 0 to n-1.
For each i, initialize a variable current_xor to 0. This variable will accumulate the XOR of elements from i to j.
Iterate over the second index j from i to n-1.
Update current_xor as current_xor XOR nums[j].
Iterate over the third index k from j to n-1.
Compute triplet_value = current_xor XOR nums[k] and insert it into triplet_xors.
After all iterations, return the size of triplet_xors.

Why it works: By iterating i <= j <= k and maintaining current_xor for the first two elements, we efficiently compute all possible XOR triplets without recomputing the same partial XOR repeatedly. The set ensures uniqueness automatically.

Python Solution

from typing import List

class Solution:
    def uniqueXorTriplets(self, nums: List[int]) -> int:
        distinct_values = list(set(nums))
        MAX_XOR = 2048

        pair_xor = [False] * MAX_XOR

        for a in distinct_values:
            for b in distinct_values:
                pair_xor[a ^ b] = True

        triple_xor = [False] * MAX_XOR

        for xor_value in range(MAX_XOR):
            if pair_xor[xor_value]:
                for value in distinct_values:
                    triple_xor[xor_value ^ value] = True

        return sum(triple_xor)

The implementation begins by removing duplicate values because only the existence of a value matters. It then builds the set of all possible pair XOR results.

Once every reachable a XOR b value has been identified, the code combines those results with every available value c. This generates every possible expression of the form a XOR b XOR c.

Finally, counting the marked positions in triple_xor gives the number of unique XOR triplet values. n = len(nums) triplet_xors = set()

    for i in range(n):
        current_xor = 0
        for j in range(i, n):
            current_xor ^= nums[j]
            temp_xor = current_xor
            for k in range(j, n):
                triplet_xors.add(temp_xor ^ nums[k])
    
    return len(triplet_xors)


This implementation mirrors the algorithm walkthrough. The outer loop selects the starting index `i`, `current_xor` accumulates XOR from `i` to `j`, and the innermost loop extends this XOR with `nums[k]`. All results are stored in a set, guaranteeing uniqueness. Finally, the size of the set provides the number of distinct XOR triplet values.

## Go Solution

```go
func uniqueXorTriplets(nums []int) int {
	const MAX_XOR = 2048

	seen := make(map[int]bool)
	distinct := make([]int, 0)

	for _, v := range nums {
		if !seen[v] {
			seen[v] = true
			distinct = append(distinct, v)
		}
	}

	pairXor := make([]bool, MAX_XOR)

	for _, a := range distinct {
		for _, b := range distinct {
			pairXor[a^b] = true
		}
	}

	tripleXor := make([]bool, MAX_XOR)

	for xorValue := 0; xorValue < MAX_XOR; xorValue++ {
		if pairXor[xorValue] {
			for _, v := range distinct {
				tripleXor[xorValue^v] = true
			}
		}
	}

	answer := 0
	for _, reachable := range tripleXor {
		if reachable {
			answer++
		}
	}

	return answer
}

The Go version follows exactly the same logic as the Python solution. A map is used to deduplicate values, and fixed-size boolean slices of length 2048 are used to represent reachable XOR states. Since the maximum XOR value is bounded by 2047, there is no risk of index overflow.

Worked Examples

Example 1

Input:

nums = [1, 3]

Distinct values:

{1, 3}

Step 1: Pair XORs

a	b	a XOR b
1	1	0
1	3	2
3	1	2
3	3	0

Reachable pair XOR values:

{0, 2}

Step 2: Triple XORs

Using pair XOR = 0:

Pair XOR	c	Result
0	1	1
0	3	3

Using pair XOR = 2:

Pair XOR	c	Result
2	1	3
2	3	1

Reachable triplet XOR values:

{1, 3}

Answer:

Example 2

Input:

nums = [6, 7, 8, 9]

Distinct values:

{6, 7, 8, 9}

Pair XOR values become:

{0, 1, 14, 15}

Combining with all array values:

Pair XOR	Generated Values
0	{6,7,8,9}
1	{6,7,8,9}
14	{8,9,6,7}
15	{9,8,7,6}

Final reachable values:

{6, 7, 8, 9}

Answer:

n := len(nums)
tripletXors := make(map[int]struct{})

for i := 0; i < n; i++ {
    currentXor := 0
    for j := i; j < n; j++ {
        currentXor ^= nums[j]
        tempXor := currentXor
        for k := j; k < n; k++ {
            tripletXors[tempXor ^ nums[k]] = struct{}{}
        }
    }
}

return len(tripletXors)

}


The Go version uses a `map[int]struct{}` to emulate a set of integers. The logic follows Python exactly. Go-specific considerations include using an empty struct to save memory, avoiding nil slices by initializing with `make`, and type correctness.

## Worked Examples

### Example 1: nums = [1, 3]

| i | j | k | current_xor | triplet_value | triplet_xors |
| --- | --- | --- | --- | --- | --- |
| 0 | 0 | 0 | 1 | 1 | {1} |
| 0 | 0 | 1 | 1 | 1 ^ 3 = 2 | {1, 2} |
| 0 | 1 | 1 | 1 ^ 3 = 2 | 2 ^ 3 = 1 | {1, 2} |
| 1 | 1 | 1 | 3 | 3 | {1, 2, 3} |

After filtering unique values, the final set is `{1, 3}`, length = 2.

### Example 2: nums = [6, 7, 8, 9]

Following the algorithm, all XOR triplet values reduce to `{6, 7, 8, 9}`, length = 4.

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(m² + 2048·m) | Pair generation plus combining pair XOR values with array values |
| Space | O(2048) | Two fixed-size boolean arrays |

Here `m` is the number of distinct values in the array.

Because the XOR space is bounded at 2048 values, the memory usage remains constant regardless of input size. The dominant cost comes from generating all pair XOR values among distinct numbers.

## Test Cases

```python
from typing import List

s = Solution()

assert s.uniqueXorTriplets([1, 3]) == 2          # example 1
assert s.uniqueXorTriplets([6, 7, 8, 9]) == 4    # example 2

assert s.uniqueXorTriplets([1]) == 1             # single element
assert s.uniqueXorTriplets([5, 5, 5]) == 1       # all duplicates
assert s.uniqueXorTriplets([1, 2]) == 2          # small two-value case

assert s.uniqueXorTriplets([1, 2, 3]) == 4       # several XOR outcomes
assert s.uniqueXorTriplets([7, 7, 8, 8]) == 2    # duplicate values only

assert s.uniqueXorTriplets([1500]) == 1          # maximum value
assert s.uniqueXorTriplets(list(range(1, 50))) > 0  # larger input sanity check

Test Summary

Test	Why
`[1,3]`	Validates example 1
`[6,7,8,9]`	Validates example 2
`[1]`	Smallest possible array
`[5,5,5]`	All elements identical
`[1,2]`	Small array with distinct values
`[1,2,3]`	Multiple reachable XOR states
`[7,7,8,8]`	Heavy duplication
`[1500]`	Maximum allowed value
`range(1,50)`	Larger sanity test

Edge Cases

A single-element array is an important edge case. Since triplets may reuse indices, (0,0,0) is a valid triplet. The only possible XOR value is the element itself because x XOR x XOR x = x. The implementation handles this naturally because the distinct-value set contains exactly one element.

Arrays containing many duplicate values can be a source of bugs if a solution incorrectly treats each occurrence as unique. Since index reuse is already allowed, duplicates do not create new XOR possibilities. By converting the input into a set of distinct values first, the implementation avoids unnecessary work and correctly models the reachable XOR states.

Values near the upper bound of 1500 are another important case. A common mistake is assuming XOR results remain below the largest input value. XOR can produce larger numbers, but because all inputs fit within 11 bits, every result remains below 2048. The implementation allocates arrays of size 2048, guaranteeing that every possible XOR state has a valid index.

Finally, large inputs with up to 1500 elements make brute-force enumeration impossible. The solution exploits the fact that the XOR state space is limited to only 2048 values, allowing it to remain efficient even at the maximum constraint limits. | Time | O(n^3) worst case | Each index triplet (i, j, k) is visited; n <= 1500 still feasible with set optimizations | | Space | O(n^2) | The set stores all unique XOR results; worst case quadratic in n |

While the worst case is cubic, practical performance is better due to repeated XOR values collapsing into fewer unique entries.

Test Cases

# Provided examples
assert Solution().uniqueXorTriplets([1, 3]) == 2  # Example 1
assert Solution().uniqueXorTriplets([6, 7, 8, 9]) == 4  # Example 2

# Edge cases
assert Solution().uniqueXorTriplets([1]) == 1  # Single element
assert Solution().uniqueXorTriplets([1, 1, 1]) == 1  # All elements identical
assert Solution().uniqueXorTriplets([1, 2, 3]) == 4  # Small array with distinct elements

# Stress case
assert Solution().uniqueXorTriplets(list(range(1, 11))) == len(set(
    [i ^ j ^ k for i in range(1, 11) for j in range(1, 11) for k in range(1, 11)]
))

Test	Why
[1, 3]	Basic example verifying correct enumeration
[6, 7, 8, 9]	Small distinct elements, validates uniqueness
[1]	Single-element array edge case
[1, 1, 1]	Identical elements, ensures deduplication
[1, 2, 3]	Checks combinatorial counting
range(1, 11)	Stress test, validates correctness on multiple unique values

Edge Cases

Single-element array: Only one possible triplet exists (0,0,0). The implementation correctly returns 1 because the set stores the single XOR value.
All identical elements: Multiple triplets collapse to the same XOR value. Using a set ensures that duplicates do not inflate the count.
Large arrays with sequential numbers: Could produce many duplicate XOR values. The algorithm efficiently handles this using cumulative XOR and set insertion, avoiding redundant