3514. Number of Unique XOR Triplets II

題目 / Problem

中文： 給定一個整數陣列 nums。一個「XOR 三元組」定義為 nums[i] XOR nums[j] XOR nums[k]，其中索引滿足 i <= j <= k（索引可以重複）。請回傳所有可能三元組所產生的不同 XOR 值的數量。

English: You are given an integer array nums. A XOR triplet is nums[i] XOR nums[j] XOR nums[k] where i <= j <= k (indices may repeat). Return the number of unique XOR triplet values over all valid (i, j, k).

限制 / Constraints: - 1 <= nums.length <= 1500 - 1 <= nums[i] <= 1500

範例 / Example: nums = [1,3] - (0,0,0) → 1^1^1 = 1 - (0,0,1) → 1^1^3 = 3 - (0,1,1) → 1^3^3 = 1 - (1,1,1) → 3^3^3 = 3

不同的值是 {1, 3}，所以答案是 2 / The unique values are {1, 3}, so the answer is 2.

名詞解釋 / Glossary

XOR（互斥或 / exclusive or, ^） — 逐位元比較兩個數，位元不同得 1、相同得 0。它有兩個關鍵性質：交換律（a^b == b^a）與 a^a == 0。A bitwise operation on two numbers: each bit is 1 when the two input bits differ. It is commutative and satisfies a^a == 0.
多重集合（multiset） — 允許重複元素的集合。因為 i <= j <= k 只是要求索引由小到大排列，實際上我們是在挑「任意 3 個可重複的元素」。A set that allows repeats; the i<=j<=k rule just means "pick any 3 elements, repeats allowed."
集合去重 / set (dedup) — 一種只保留不同元素的容器。我們用它避免重複計算相同的值。A container that keeps only distinct values, so we never count a value twice.
布林標記陣列 / boolean marker array — 一個以「值」當索引的 0/1 陣列，arr[v]=1 表示值 v 出現過。因為所有值都很小（< 2048），我們可以用它取代雜湊表，速度更快。An array indexed by value; arr[v]=1 means value v has appeared. Since all values are small (< 2048), this replaces a hash set and is faster.
位元寬度 / bit width — nums[i] <= 1500 < 2048 = 2^11，所以每個數最多 11 個位元；三個這種數 XOR 後仍 < 2048。Each value fits in 11 bits, so any XOR of them stays below 2048.

思路

中文： 最直接的暴力法是三層迴圈枚舉所有 (i, j, k)，計算 nums[i]^nums[j]^nums[k] 並丟進集合，這是 O(n³)。當 n = 1500 時約 33 億次運算，會超時。關鍵觀察是：條件 i <= j <= k 其實只是「把三個索引由小到大排序」，所以我們挑的是任意三個可重複的元素（一個大小為 3 的多重集合）。既然 XOR 有交換律，元素的順序不重要，我們甚至不需要在意原本的索引——只要在意有哪些不同的數值。第二個關鍵是值域很小：nums[i] <= 1500 < 2048，而 XOR 不會讓位元變多，所以任何三元組的結果也 < 2048。於是做法變成兩步：先算出所有「兩數 XOR」的集合 P = {a^b}（用一個大小 2048 的布林陣列標記），再把 P 裡的每個值和每個不同的 nums 值再 XOR 一次，得到三元組值的集合 T = {p^c}。最後數 T 裡有幾個被標記的值就是答案。先去重數值可以把外層迴圈從 n 降到「不同值的個數 m」（最多 1500，但常常更少），而值域上限 2048 讓內層迴圈有固定上界。

English: The naive approach loops over all (i, j, k) in O(n³), which is ~3.3 billion operations at n = 1500 — too slow. The key insight is that i <= j <= k merely says "sort the three chosen indices," so we are really picking any 3 elements with repetition (a size-3 multiset). Because XOR is commutative, order doesn't matter and neither do the original indices — only the distinct values matter. The second key fact is that the value range is tiny: nums[i] <= 1500 < 2048, and XOR never adds high bits, so every triplet result is also < 2048. This turns the problem into two passes. First build the set of all pairwise XORs P = {a^b} using a size-2048 boolean marker array. Then XOR each value in P with each distinct nums value to get the triplet set T = {p^c}. The answer is the number of marked entries in T. Deduplicating values first shrinks the loops from n to the number of distinct values m, and the fixed 2048 bound caps the inner work.

逐步走查 / Walkthrough

輸入 / Input: nums = [1, 3]

步驟 / Step	動作 / Action	狀態 / State
1	標記出現過的值 / mark present values	`present[1]=1, present[3]=1`
2	收集不同值 / collect distinct	`distinct = [1, 3]`, `m = 2`
3	兩數 XOR：`1^1` / pair xor	`0` → `pair[0]=1`
4	兩數 XOR：`1^3`	`2` → `pair[2]=1`
5	兩數 XOR：`3^3`	`0` → `pair[0]=1`（已標記 / already set）
—	目前配對集合 / pair set so far	`P = {0, 2}`
6	三元組：`p=0 ^ c=1`	`1` → `triple[1]=1`
7	三元組：`p=0 ^ c=3`	`3` → `triple[3]=1`
8	三元組：`p=2 ^ c=1`	`3` → `triple[3]=1`（重複 / duplicate）
9	三元組：`p=2 ^ c=3`	`1` → `triple[1]=1`（重複 / duplicate）
—	三元組集合 / triple set	`T = {1, 3}`
10	計數 / count marked	`2` ✅

Solution — C

// 演算法 / Algorithm:
// 1) 去重，得到不同的數值 distinct[] / dedup to distinct values.
// 2) 對每對不同值做 XOR，記錄所有「兩數 XOR」結果 / all pairwise XORs.
// 3) 再把每個兩數結果與每個不同值 XOR，記錄「三元組 XOR」/ all triplet XORs.
// 4) 數三元組集合中被標記的值 / count marked triplet values.

// 值域上限：nums[i] <= 1500 < 2048，三個值 XOR 後仍 < 2048。
// Value bound: nums[i] < 2048, so any XOR of them stays < 2048.
#define LIM 2048

int uniqueXorTriplets(int* nums, int numsSize) {
    // present[v]=1 表示數值 v 在 nums 裡出現過 / v appears in nums.
    // 用值當索引的布林陣列，比雜湊表更快 / value-indexed boolean array, faster than a hash set.
    char present[LIM] = {0};                 // {0} 把整個陣列初始化為 0 / initialize all to 0.
    for (int i = 0; i < numsSize; i++)       // 掃過每個元素 / scan each element.
        present[nums[i]] = 1;                // 標記它出現過 / mark it as seen.

    // 把出現過的值收集成一個緊湊的清單 / collect seen values into a compact list.
    int distinct[LIM];                       // 最多 2048 個不同值 / at most 2048 distinct values.
    int m = 0;                               // m 是不同值的個數 / m = count of distinct values.
    for (int v = 0; v < LIM; v++)            // 依序檢查每個可能值 / check every possible value.
        if (present[v]) distinct[m++] = v;   // 若出現過就加入清單 / append if seen.

    // pair[x]=1 表示某對不同值的 XOR 等於 x / x is achievable as a^b.
    char pair[LIM] = {0};
    for (int a = 0; a < m; a++)              // 選第一個值 distinct[a] / pick first value.
        for (int b = a; b < m; b++)          // 選第二個值（b 從 a 開始，允許 a==b）/ second value, b>=a allows repeat.
            pair[distinct[a] ^ distinct[b]] = 1;   // ^ 是位元 XOR，標記這個配對結果 / mark this pairwise XOR.

    // triple[x]=1 表示某個三元組的 XOR 等於 x / x is achievable as a^b^c.
    char triple[LIM] = {0};
    for (int p = 0; p < LIM; p++) {          // 掃過所有可能的「兩數 XOR」值 / scan all pair values.
        if (!pair[p]) continue;              // 跳過沒被標記的值 / skip values never produced.
        for (int c = 0; c < m; c++)          // 再 XOR 上每個不同值 / XOR with each distinct value.
            triple[p ^ distinct[c]] = 1;     // 標記三元組結果 / mark this triplet XOR.
    }

    // 數出被標記的三元組值有幾個 / count how many triplet values are marked.
    int count = 0;
    for (int x = 0; x < LIM; x++)            // 掃過整個值域 / scan the whole range.
        if (triple[x]) count++;              // 每個被標記的值代表一個不同答案 / each marked value = one unique result.
    return count;                            // 這就是不同三元組 XOR 值的數量 / the answer.
}

Solution — C++

// 演算法與 C 版相同：去重 → 兩數 XOR 集合 → 三元組 XOR 集合 → 計數。
// Same algorithm as the C version: dedup → pairwise XOR set → triplet XOR set → count.
#include <vector>
#include <bitset>
using namespace std;

class Solution {
public:
    int uniqueXorTriplets(vector<int>& nums) {
        const int LIM = 2048;                // 值域上限（2^11），因為值 < 2048 / value bound, since values < 2048.

        // bitset<LIM> 是固定大小的位元集合，每個位置只佔 1 bit，且自動歸零。
        // bitset<LIM> is a fixed-size bit container; each slot is 1 bit and starts as 0.
        bitset<LIM> present;                 // present[v]=1 表示 v 出現過 / v appears in nums.
        for (int v : nums)                   // range-for：依序取出每個元素 / iterate each element.
            present[v] = 1;                  // 標記出現 / mark as seen.

        // 把出現過的值收集成緊湊清單，之後迴圈只跑不同值 / compact list of distinct values.
        vector<int> distinct;                // vector 是可自動增長的動態陣列 / a growable dynamic array.
        for (int v = 0; v < LIM; v++)
            if (present[v]) distinct.push_back(v);   // push_back 在尾端加入一個元素 / append at the end.

        // pair[x]=1 表示 x 可由某對不同值 XOR 得到 / x achievable as a^b.
        bitset<LIM> pair;
        for (size_t a = 0; a < distinct.size(); a++)         // 第一個值 / first value.
            for (size_t b = a; b < distinct.size(); b++)     // 第二個值，b>=a 允許重複 / second value, repeats allowed.
                pair[distinct[a] ^ distinct[b]] = 1;         // ^ 為位元 XOR / bitwise XOR, mark result.

        // triple[x]=1 表示 x 可由某三元組 XOR 得到 / x achievable as a^b^c.
        bitset<LIM> triple;
        for (int p = 0; p < LIM; p++) {      // 掃過所有可能的兩數 XOR 值 / scan all pair values.
            if (!pair[p]) continue;          // 沒被標記就跳過 / skip if never produced.
            for (int c : distinct)           // 再 XOR 上每個不同值 / XOR with each distinct value.
                triple[p ^ c] = 1;           // 標記三元組結果 / mark this triplet XOR.
        }

        // bitset 的 count() 直接回傳有幾個位元是 1 / count() returns the number of set bits.
        return (int)triple.count();          // 即不同三元組 XOR 值的數量 / the answer.
    }
};

複雜度 / Complexity

Time: O(m² + V·m)，其中 m 是不同值的個數（≤ 1500），V = 2048 是值域大小。兩數 XOR 的雙層迴圈是 O(m²)（約 100 萬次），三元組迴圈最多 V·m 次。整體遠優於暴力的 O(n³)。Here m is the number of distinct values and V = 2048 is the value range; the pairwise loop dominates at O(m²), far better than the naive O(n³).
Space: O(V) — 三個大小 2048 的布林/位元陣列加上不同值清單，都是常數等級的固定空間。Three size-2048 marker arrays plus the distinct-value list — effectively constant extra space.

Pitfalls & Edge Cases

值域大小要抓對 / Get the array bound right — nums[i] <= 1500，但答案值域是 XOR 結果，最大到 2047，所以陣列要開到 2048 而非 1501。開太小會越界寫入（undefined behavior）。The result range goes up to 2047, so size the arrays to 2048, not 1501.
索引可以重複 / Indices may repeat — i <= j <= k 允許 i==j==k，因此配對迴圈用 b 從 a（含）開始，別寫成 a+1，否則會漏掉像 a^a=0 這種情況。Start the inner loop at b = a, not a+1, or you miss cases like a^a.
一定要先去重 / Deduplicate first — 不去重雖然答案仍正確，但迴圈會變成 O(n²)；當有大量重複值時去重能大幅加速。Correctness is unaffected, but skipping dedup makes the loops O(n²) and slow on repeat-heavy inputs.
單一元素 / Single element (n == 1) — 唯一三元組是 nums[0]^nums[0]^nums[0] = nums[0]，答案為 1；本解法自然涵蓋（P={0}, T={nums[0]}）。The lone triplet yields nums[0], answer 1; the code handles it naturally.
不要數配對集合 / Don't count the pair set by mistake — 最終答案來自 triple，不是 pair；混淆兩者會回傳錯誤數字。The answer comes from triple, not pair — mixing them up returns the wrong count.