3513. Number of Unique XOR Triplets I

題目 / Problem

中文： 給你一個長度為 n 的整數陣列 nums，它是數字 [1, n] 的一個排列（即 1 到 n 每個數字恰好各出現一次）。

定義一個 XOR 三元組 為 nums[i] XOR nums[j] XOR nums[k]，其中下標滿足 i <= j <= k（允許重複取同一個位置）。

請回傳所有可能三元組得到的不同 XOR 值的個數。

English: You are given an integer array nums of length n, which is a permutation of the numbers [1, n] (each of 1..n appears exactly once).

A XOR triplet is nums[i] XOR nums[j] XOR nums[k] with indices i <= j <= k (indices may repeat).

Return how many distinct XOR values are produced across all such triplets.

Constraints: - 1 <= n == nums.length <= 10^5 - 1 <= nums[i] <= n - nums is a permutation of 1..n.

Worked example: nums = [3,1,2] - (0,1,2) → 3 XOR 1 XOR 2 = 0 - (0,0,1) → 3 XOR 3 XOR 1 = 1 - (0,0,2) → 3 XOR 3 XOR 2 = 2 - (0,0,0) → 3 XOR 3 XOR 3 = 3

Distinct values {0, 1, 2, 3} → output 4.

名詞解釋 / Glossary

• 排列 / permutation：把 1, 2, ..., n 每個數字恰好用一次、打亂順序排成的陣列。因此陣列的內容是固定的，只有順序不同。 / An arrangement using each of 1..n exactly once; only the order varies.
• XOR（互斥或）/ bitwise XOR (^)：一種按位運算。兩個位元相同得 0、不同得 1。重要性質：x ^ x = 0（自己和自己抵消）且 x ^ 0 = x。 / A per-bit operation: equal bits give 0, different bits give 1. Key facts: x ^ x = 0 and x ^ 0 = x.
• 最高有效位 / most significant bit (MSB)：一個數字二進位表示中最左邊那個為 1 的位元的位置（從 0 開始數）。例如 6 = 110₂，最高位在第 2 位，msb(6) = 2。 / The index (0-based) of the highest set bit. E.g. 6 = 110₂ has msb = 2.
• 位移 / bit shift (<<)：1 << k 等於 2^k，也就是把二進位的 1 往左推 k 格。這是計算 2 的次方最快的方式。 / 1 << k equals 2^k; the fastest way to compute a power of two.
• 值域 / value range：所有可能結果落在的區間。這題我們會證明結果剛好填滿一段連續區間 [0, 2^B - 1]。 / The interval that all results fall into; here it is exactly [0, 2^B - 1].

思路

最直接的暴力法是三層迴圈枚舉所有 i <= j <= k，把每個 nums[i]^nums[j]^nums[k] 丟進一個雜湊集合去重，最後回傳集合大小。但三元組數量約為 n^3，當 n = 10^5 時高達 10^15，完全不可行。所以我們必須找出結果集合的「形狀」，而不是逐一枚舉。先做兩個觀察。第一，因為允許 i = j，取兩個相同位置再配一個任意位置會得到 x ^ x ^ y = y，所以每個陣列元素本身都是可達值；同理 i = j = k 給出 x。第二，當 n >= 3 時，陣列一定同時包含 1、2、3 這些小數字，配合「三個相異元素相 XOR」的自由度，我們其實可以拼出從 0 開始的每一個數字，直到用光 n 所需的位元數為止。設 B = msb(n) + 1 為表示 n 所需的位元數，官方結論是：可達值恰好填滿連續區間 [0, 2^B - 1]，因此不同值的個數就是 2^B。要注意 n <= 2 無法湊出三個相異元素，可達值受限，必須單獨處理：n = 1 只有一個元素，答案是 1；n = 2 只能得到 {1, 2}，答案是 2。於是整題壓縮成一個 O(n) 甚至 O(log n) 的公式，連陣列內容都不用看，只需要它的長度 n。

The brute force enumerates every i <= j <= k, XORs the three values, and stores results in a hash set — but with about n^3 triplets and n up to 10^5, that is 10^15 operations, hopelessly slow. The trick is to describe the shape of the answer set instead of listing it. Two observations. First, because i = j is allowed, x ^ x ^ y = y, so every element of the array is itself reachable (and i = j = k gives x). Second, once n >= 3, the permutation is guaranteed to contain the small numbers 1, 2, 3, and combined with the freedom of XOR-ing three distinct elements, you can actually build every value starting from 0 up to the full bit-width that n needs. Let B = msb(n) + 1 be the number of bits required to write n. The proven result is that the reachable values fill the contiguous range [0, 2^B - 1] exactly, so the count of distinct values is simply 2^B. The catch: n <= 2 cannot form three distinct elements, so those cases are limited and handled separately — n = 1 yields only {1} (answer 1) and n = 2 yields only {1, 2} (answer 2). The whole problem collapses to an O(log n) formula that never even inspects the array contents, only its length n.

逐步走查 / Walkthrough

Example input: nums = [3,1,2], so n = 3.

回傳 4，對應可達集合 {0, 1, 2, 3}，與題目說明一致。 / Return 4, matching the reachable set {0, 1, 2, 3} from the statement.

如何找 msb(3) / How the MSB loop runs: 從 t = 3、msb = 0 開始；t > 1 成立 → t = 3 >> 1 = 1、msb = 1；此時 t = 1 不再大於 1，迴圈停止，得 msb = 1。 / Start t = 3, msb = 0; since t > 1, do t = 1, msb = 1; now t = 1 is not > 1, loop stops, giving msb = 1.

Solution — C

// 演算法 / Algorithm:
// 答案只和陣列長度 n 有關。n<=2 單獨處理；否則可達 XOR 值恰好是
// [0, 2^B - 1]，其中 B = n 的位元數，故答案 = 2^B。
// The answer depends only on n. Handle n<=2 specially; otherwise the
// reachable XOR values are exactly [0, 2^B - 1] with B = bit-width of n,
// so the answer is 2^B.

int uniqueXorTriplets(int* nums, int numsSize) {
    int n = numsSize;              // n 就是排列的長度 / n is the length of the permutation

    if (n == 1) return 1;          // 只有一個元素，唯一可達值就是它自己 / single element → only 1 distinct value
    if (n == 2) return 2;          // 只能得到 {1,2} 兩個值 / only {1,2} are reachable → 2 values

    // 求 n 的最高有效位的位置（index，從 0 起算）
    // Find the index of the most significant bit of n (0-based).
    int msb = 0;                   // 最高位的位置，先假設是第 0 位 / position of top bit, start at 0
    int t = n;                     // 用副本做位移，不破壞 n / a copy so we don't destroy n
    while (t > 1) {                // 只要還不止 1 個位元，就繼續往右推 / while more than one bit remains
        t >>= 1;                   // t = t / 2，砍掉最低位 / shift right by 1 = drop the lowest bit
        msb++;                     // 每砍一次，最高位位置往上加 1 / each shift raises the top-bit index
    }

    // B = msb + 1 是表示 n 所需的位元數；答案 = 2^B。
    // B = msb + 1 is the bit-width of n; the answer is 2^B.
    // 1 << (msb + 1) 就是 2 的 (msb+1) 次方，最大到 1<<17=131072，不會溢位。
    // 1 << (msb + 1) equals 2^(msb+1); at most 1<<17 = 131072, so no int overflow.
    return 1 << (msb + 1);
}

Solution — C++

// 演算法 / Algorithm:
// 與 C 版相同：答案僅取決於 n。n<=2 單獨處理，否則可達 XOR 值填滿
// [0, 2^B - 1]（B = n 的位元數），答案為 2^B。
// Same as the C version: the answer depends only on n. Special-case n<=2,
// otherwise reachable values fill [0, 2^B - 1] (B = bit-width of n),
// giving 2^B.

#include <vector>   // std::vector：LeetCode 傳入的動態陣列型別 / dynamic array type used by LeetCode
using namespace std;

class Solution {
public:
    int uniqueXorTriplets(vector<int>& nums) {
        int n = nums.size();       // .size() 回傳容器元素個數，即 n / .size() gives the element count = n

        if (n == 1) return 1;      // 唯一可達值是那個元素本身 / only the element itself is reachable
        if (n == 2) return 2;      // 只能湊出 {1,2} 兩個值 / only {1,2} reachable → 2 values

        int msb = 0;               // 最高有效位的位置 / index of the most significant bit
        int t = n;                 // n 的副本，供位移用 / a mutable copy of n for shifting
        while (t > 1) {            // 逐次右移直到只剩最高位 / shift until only the top bit is left
            t >>= 1;               // 除以 2，丟掉最低位 / divide by 2, drop the lowest bit
            ++msb;                 // 位置往上累加 / bump the top-bit index
        }

        // 2^(msb+1)：用左移計算 2 的次方，快且精確。
        // 2^(msb+1): a left shift computes the power of two quickly and exactly.
        return 1 << (msb + 1);
    }
};

複雜度 / Complexity

• Time: O(log n) — 主要成本是那個 while 迴圈，每次把 t 減半，因此最多執行 log₂(n) 次（n = 10^5 時約 17 次）。我們完全沒有走訪陣列內容，所以連 O(n) 都不用。 / The while loop halves t each iteration, so it runs about log₂(n) times (~17 for n = 10^5). We never scan the array, so it is even below O(n).
• Space: O(1) — 只用了 n、msb、t 幾個整數變數，與輸入大小無關。 / Only a few integer variables (n, msb, t), independent of input size.

Pitfalls & Edge Cases

• 忘記處理 n <= 2 / Forgetting the n <= 2 special cases：一般公式 2^(msb+1) 對 n = 2 會算出 4，但正確答案是 2；n = 3 以下無法組出三個相異元素，可達集合較小，必須單獨回傳。 / The general formula gives 4 for n = 2, but the true answer is 2. With n < 3 you cannot pick three distinct elements, so hard-code these.
• msb 差一位 / Off-by-one in the MSB：答案要的是「位元數」msb + 1，不是 msb。若寫成 1 << msb 會少一半。務必記得 +1。 / You need the bit-width msb + 1, not msb itself; 1 << msb is half the correct value.
• 誤以為要看陣列內容 / Assuming array contents matter：因為 nums 保證是 1..n 的排列，答案只和 n 有關，讀不讀 nums[i] 都不影響結果，別浪費時間排序或建雜湊表。 / Since nums is guaranteed to be a permutation of 1..n, only n matters; don't sort or hash the values.
• 位移溢位的顧慮 / Shift overflow worry：n 最大 10^5，msb 最多 16，1 << 17 = 131072 遠在 32 位 int 範圍內，安全。但若題目上界更大就要改用 long long。 / With n ≤ 10^5, the largest shift is 1 << 17 = 131072, safely within int; a larger bound would require long long.
• t > 1 的迴圈條件 / The loop guard t > 1：條件寫成 t > 1（而非 t > 0）可保證迴圈在剩下最高位時停下，得到正確的 msb；用 t > 0 會多跑一次。 / Using t > 1 (not t > 0) stops the loop exactly when only the top bit remains; t > 0 would over-count by one.