3514. Number of Unique XOR Triplets II

Array
Bit Manipulation
Hash Table
Enumeration

TIME

O(D^2 + V * D) (D = distinct values, V = 2048)

SPACE

O(V)

Intuition

Unlike part I, nums is arbitrary, so we can't reduce to a closed-form on n. But the values are tiny: nums[i] <= 1500 < 2048 = 2^11, so every XOR result fits in 11 bits and there are at most 2048 distinct values anywhere in the computation. That bounds the whole search space and makes brute-forcing in two stages feasible.

Since i <= j <= k allows repeats and XOR is commutative, the reachable values are exactly {a ^ b ^ c} over any multiset of three elements. Splitting that as (a ^ b) ^ c lets us do it in two passes instead of an O(n^3) triple loop:

All pairwise XORs, at most 2048 distinct values (not n^2).
XOR each of those against every element.

Deduplicating nums first is what keeps stage 1 manageable.

Approach

distinct = deduplicated nums (at most 1500 values).
Pair set: pairs = { a ^ b : a, b in distinct }. Including a ^ a gives 0, which covers the "reuse the same index twice" case.
Triplet set: result = { p ^ c : p in pairs, c in distinct }.
Return len(result).

Stage 2 is cheap because |pairs| <= 2048 regardless of how large n is.

Complexity

Time: O(D² + V · D) where D = distinct values (≤ 1500) and V = 2048 → about 5M operations
Space: O(V), bounded by 2048 entries

Edge Cases

Single element [a] → a ^ a ^ a = a → 1 value
All identical values → deduplication collapses to one → 1 value
0 is always in pairs (from a ^ a), so every single element is reachable as a triplet
Values up to 1500 mean results stay under 2048, a fixed-size boolean array suffices instead of a hash set

Code

from typing import List


class Solution:
    def uniqueXorTriplets(self, nums: List[int]) -> int:
        """
        3514. Number of Unique XOR Triplets II
        Time: O(D^2 + V * D)  (D = distinct values, V = 2048)
        Space: O(V)
        """
        distinct = list(set(nums))

        # All pairwise XORs; a ^ a = 0 covers reusing one index twice.
        pairs = {a ^ b for a in distinct for b in distinct}

        # XOR every pair value against every element.
        result = {p ^ c for p in pairs for c in distinct}

        return len(result)

/**
 * 3514. Number of Unique XOR Triplets II
 * Time: O(D^2 + V * D)  (D = distinct values, V = 2048)
 * Space: O(V)
 */
class Solution {
    private static final int V = 2048; // values <= 1500 < 2^11

    public int uniqueXorTriplets(int[] nums) {
        // Deduplicate.
        boolean[] present = new boolean[V];
        for (int x : nums) {
            present[x] = true;
        }
        int d = 0;
        int[] distinct = new int[V];
        for (int v = 0; v < V; v++) {
            if (present[v]) {
                distinct[d++] = v;
            }
        }

        // All pairwise XORs; a ^ a = 0 covers reusing one index twice.
        boolean[] pairs = new boolean[V];
        for (int i = 0; i < d; i++) {
            for (int j = 0; j < d; j++) {
                pairs[distinct[i] ^ distinct[j]] = true;
            }
        }

        // XOR every pair value against every element.
        boolean[] result = new boolean[V];
        for (int p = 0; p < V; p++) {
            if (!pairs[p]) {
                continue;
            }
            for (int i = 0; i < d; i++) {
                result[p ^ distinct[i]] = true;
            }
        }

        int count = 0;
        for (boolean b : result) {
            if (b) {
                count++;
            }
        }
        return count;
    }
}