LeetCode Problem 3513

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

Solution

Problem Understanding

The problem asks us to determine the number of unique values that can result from taking the XOR of three elements in a given array nums, where the triplets (i, j, k) must satisfy i <= j <= k. Importantly, nums is a permutation of integers from 1 to n, meaning every integer in this range appears exactly once. This ensures there are no duplicates and the values are bounded by 1 and n.

The input is an integer array nums of length n, and the output is a single integer representing the count of distinct XOR results obtained from all valid triplets. The constraints (1 <= n <= 10^5) indicate that any solution iterating through all possible triplets (O(n^3)) would be computationally infeasible. The problem guarantees nums is a permutation, so we will always have n unique integers and no need to check for repeated values.

Edge cases to consider include the smallest array (n = 1), arrays of length 2, and permutations where XOR results may overlap (e.g., when XORing multiple elements produces zero). These could trip up a naive solution if uniqueness is not handled carefully.

Approaches

Brute-Force Approach

The brute-force approach is to enumerate all triplets (i, j, k) with i <= j <= k, compute nums[i] XOR nums[j] XOR nums[k] for each, and store the results in a set to automatically handle uniqueness. While this approach is correct because it literally computes all possibilities, it is inefficient: there are roughly O(n^3) triplets, which is infeasible for n = 10^5.

Optimal Approach

The key insight comes from observing that XOR is both associative and commutative, and that the array is a permutation. Using properties of prefix XORs, we can note that the XOR of elements between indices i and k can be efficiently computed. However, in this problem, an even stronger observation simplifies it: for any permutation of [1..n], the set of all XOR triplets is exactly the set {0, 1, 2, ..., n}. This arises because the XOR operation on distinct integers generates all values up to n.

Hence, the problem reduces to computing the size of this set, which is always n or n + 1, depending on the inclusion of zero (for triplets where XOR cancels out). This drastically reduces computation from O(n^3) to O(n).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^3)	O(n^3)	Enumerates all triplets explicitly; impractical for large n
Optimal	O(n)	O(n)	Uses XOR properties and set behavior; handles uniqueness efficiently

Algorithm Walkthrough

1. Initialize an empty set xor_values to store unique XOR results. This ensures duplicates are automatically removed.
2. Iterate over all possible triplets (i, j, k) logically, but do not enumerate them explicitly. Instead, use the property of permutation and XOR to compute the potential XOR values efficiently.
3. Add each computed XOR result to xor_values.
4. After considering all triplets, the number of unique XOR triplets is the size of xor_values.
5. Return len(xor_values) as the final result.

Why it works: The set invariant ensures only unique XOR values are retained. Because XOR is associative and commutative, all triplet combinations are represented correctly without needing explicit enumeration. The properties of permutations guarantee that XOR values span the full necessary range. This problem asks for the number of distinct XOR results that can be formed by taking any triplet of indices i <= j <= k in an array nums, and computing nums[i] XOR nums[j] XOR nums[k].

The key detail is that nums is a permutation of the integers from 1 to n, meaning every integer in this range appears exactly once. However, the index condition i <= j <= k allows repetition of indices, which effectively means we can reuse the same value multiple times in the XOR operation.

Restated more simply, we are trying to find how many unique values can be generated by:

taking any three elements from the set {1, 2, ..., n}, where repetition is allowed, and computing their XOR.

The output is not the number of triplets, but the number of distinct XOR results.

The constraints are large, with n up to 10^5, which immediately rules out any cubic or even quadratic enumeration. This signals that the solution must rely on a mathematical or structural property of XOR rather than simulation.

The important edge cases include very small arrays such as n = 1 and n = 2, where the behavior does not yet exhibit the full structure seen for larger n. These cases often break naive generalizations and must be handled carefully.

Approaches

Brute Force Approach

The brute force idea is straightforward: generate all triplets (i, j, k) such that i <= j <= k, compute nums[i] XOR nums[j] XOR nums[k], and insert each result into a set to track uniqueness.

This approach is correct because it directly follows the definition of the problem. However, it is computationally infeasible because the number of triplets grows as O(n^3) in the worst case. With n = 10^5, this is far beyond acceptable limits.

Key Insight (Optimal Approach)

Because nums is a permutation of 1..n, the problem is equivalent to choosing any three numbers from the full set {1..n} with repetition allowed.

We analyze what XOR results are possible:

If we consider allowed repetitions, we get three structural cases:

When all three elements are the same, a XOR a XOR a = a, so every number in 1..n is directly achievable.

When two elements are the same and one is different, a XOR a XOR b = b, so again no new values are introduced beyond single elements.

The only potentially new values come from XORs of three distinct elements.

A crucial algebraic observation is that XOR over a set behaves like addition in a vector space over GF(2). Once the set contains enough elements to span all bit positions present in [1..n], repeated XOR combinations quickly generate the full space up to the next power of two.

This leads to a well-known structural result: for n >= 3, the set of all possible XOR triplets becomes all integers from 0 up to 2^k - 1, where 2^k is the smallest power of two strictly greater than or equal to n.

Thus, the answer becomes purely a function of the bit-length of n.

Complexity Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(n³)	Enumerates all triplets explicitly
Optimal	O(1)	O(1)	Uses XOR vector space structure and bit properties

Algorithm Walkthrough

The optimal solution relies on recognizing that the XOR closure of {1..n} under triple combinations stabilizes into a full binary space.

We proceed as follows:

1. Observe that because repetition of indices is allowed, each element in nums can be used multiple times in forming XOR triplets. This effectively turns the problem into choosing elements from the full set {1..n} with repetition.
2. Recognize that XOR has algebraic properties similar to addition in a vector space over bits. This means combinations of elements generate a span over binary representations.
3. Note that for n >= 3, the system becomes rich enough to generate all values in a complete range [0, 2^k - 1], where 2^k is the next power of two above n.
4. Therefore, the number of distinct XOR values equals that full range size.
5. Compute the smallest power of two greater than or equal to n using bit operations.
6. Return that value directly.

Why it works

The key invariant is that XOR combinations over a sufficiently large generating set form a linear space over GF(2). Once the set {1..n} includes enough independent bit patterns, triple XOR combinations can reach every representable value below the next power of two. This collapses the problem from combinatorial enumeration into a bit-length computation.

Python Solution

from typing import List

class Solution:
    def uniqueXorTriplets(self, nums: List[int]) -> int:
        n = len(nums)
        xor_values = 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):
                    temp_xor ^= nums[k] if k > j else 0
                    xor_values.add(temp_xor)
        return len(xor_values)

Implementation explanation:

We maintain a rolling XOR for indices from i to j (current_xor) to avoid recomputing from scratch. For the last index k, we update temp_xor as needed. Each temp_xor is added to the set xor_values. Finally, the number of unique XOR values is returned. This implementation leverages the set to automatically handle uniqueness, while reducing redundant computations by rolling XOR accumulation. return 1 << (n - 1).bit_length()

### Explanation of Implementation

The solution first computes `n`, the size of the permutation. The core idea is that the answer depends only on `n`, not the actual arrangement of values.

The expression `(n - 1).bit_length()` computes the number of bits required to represent `n - 1`, which effectively corresponds to `ceil(log2(n))`. Shifting `1` left by that value yields the smallest power of two greater than or equal to `n`.

This directly implements the structural result derived in the algorithm section.

## Go Solution

```go
func uniqueXorTriplets(nums []int) int {
    n := len(nums)
    xorValues := 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++ {
                if k > j {
                    tempXor ^= nums[k]
                }
                xorValues[tempXor] = struct{}{}
            }
        }
    }
    return len(xorValues)
}

Go-specific notes: We use a map[int]struct{} to simulate a set. The algorithm structure mirrors Python, using nested loops and rolling XOR accumulation. Go’s lack of a built-in set is handled with a map with empty struct values to minimize memory usage. if n == 0 { return 0 }

// compute smallest power of two >= n
power := 1
for power < n {
    power <<= 1
}
return power

}

### Go-specific Notes

In Go, there is no built-in bit-length function equivalent to Python’s `.bit_length()`, so we compute the next power of two iteratively by left-shifting until we reach or exceed `n`.

We also explicitly handle the empty slice case for safety, although the constraints guarantee `n >= 1`.

Since values remain within safe integer bounds (`n <= 1e5`), no overflow concerns arise for 32-bit or 64-bit integers in this computation.

## Worked Examples

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

| Triplet (i,j,k) | XOR Value |
| --- | --- |
| (0,0,0) | 1 |
| (0,0,1) | 2 |
| (0,1,1) | 1 |
| (1,1,1) | 2 |

Unique XOR values: `{1,2}` → Output: `2`

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

| Triplet (i,j,k) | XOR Value |
| --- | --- |
| (0,0,0) | 3 |
| (0,0,1) | 2 |
| (0,0,2) | 0 |
| (0,1,1) | 2 |
| (0,1,2) | 0 |
| (0,2,2) | 2 |
| (1,1,1) | 1 |
| (1,1,2) | 3 |
| (1,2,2) | 1 |
| (2,2,2) | 2 |

Unique XOR values: `{0,1,2,3}` → Output: `4`
Here `n = 2`. The algorithm computes the smallest power of two greater than or equal to 2, which is 2.

So the result is 2.

The valid XOR results from enumeration are `{1, 2}`, matching the computed answer.

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

Here `n = 3`. The smallest power of two greater than or equal to 3 is 4.

So the result is 4.

Conceptually, XOR combinations generate all values in `{0, 1, 2, 3}`, which matches the size 4.

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n^3) | Three nested loops over n elements |
| Space | O(n^3) | Worst-case size of the set storing unique XOR values |

Even with optimization via rolling XOR, the worst-case time complexity remains cubic for general input, but it is feasible for smaller `n`. Further mathematical analysis could reduce this to O(n) for permutation-specific inputs.
| Time | O(1) | Only computes bit-length or power of two |
| Space | O(1) | No auxiliary data structures are used |

The solution avoids iteration over triplets entirely and reduces the problem to a single arithmetic computation based on input size.

## Test Cases

Provided examples

assert Solution().uniqueXorTriplets([1,2]) == 2 # small permutation assert Solution().uniqueXorTriplets([3,1,2]) == 4 # n=3

Edge cases

assert Solution().uniqueXorTriplets([1]) == 1 # single element assert Solution().uniqueXorTriplets([1,2,3,4]) == 8 # small n, multiple triplets assert Solution().uniqueXorTriplets([5,4,3,2,1]) == 16 # descending permutation assert Solution().uniqueXorTriplets([1]) == 1 # single element case assert Solution().uniqueXorTriplets([1, 2]) == 2 # smallest non-trivial case assert Solution().uniqueXorTriplets([3, 1, 2]) == 4 # full span begins at n=3 assert Solution().uniqueXorTriplets([1, 2, 3, 4]) == 4 # still next power of two is 4 assert Solution().uniqueXorTriplets([1, 2, 3, 4, 5]) == 8 # crosses power-of-two boundary assert Solution().uniqueXorTriplets(list(range(1, 9))) == 8 # n=8 boundary check assert Solution().uniqueXorTriplets(list(range(1, 9))) == 8 # stable within range

| Test | Why |
| --- | --- |
| [1,2] | Tests minimal permutation with two elements |
| [3,1,2] | Tests n=3 permutation and overlapping XOR results |
| [1] | Tests single-element edge case |
| [1,2,3,4] | Tests small permutation with multiple triplets |
| [5,4,3,2,1] | Tests descending order permutation |

## Edge Cases

**Single-element array:** For `nums = [1]`, only one triplet `(0,0,0)` exists, producing a single XOR value `1`. The algorithm handles this naturally as the loops iterate correctly over the single index.

**Two-element array:** For `nums = [1,2]`, triplets include `(0,0,0)`, `(0,0,1)`, `(0,1,1)`, `(1,1,1)`. This tests correct handling of overlapping XOR values and ensures uniqueness in the output set.

**Permutation order does not matter:** The algorithm does not assume sorted input. Whether the permutation is ascending, descending, or random, the XOR results are computed correctly because XOR is commutative and the set guarantees uniqueness.

This design guarantees correctness across all valid inputs under the problem constraints.
| [1] | minimal input size |
| [1,2] | verifies non-trivial small behavior |
| [3,1,2] | shows full XOR space emerges at n=3 |
| [1,2,3,4] | checks boundary at power of two |
| [1..5] | validates growth beyond boundary |
| [1..8] | confirms stability at exact power of two |

## Edge Cases

One important edge case is `n = 1`, where only a single value exists. Any triplet must reuse this value three times, so the only XOR result is `1`. This case correctly returns `1`, matching the smallest power-of-two rule.

Another edge case is `n = 2`, where naive generalizations might incorrectly predict a power-of-two result of `4`. However, the structure is still constrained, producing only `{1, 2}`. The formula still holds because the next power of two greater than or equal to 2 is exactly 2.

A third edge case occurs at power-of-two boundaries such as `n = 4, 8, 16`. These inputs often cause off-by-one errors in bit computations. The implementation avoids this by directly computing the next power of two, ensuring correctness at exact boundaries without special-case logic.