LeetCode 解題筆記：3513. Number of Unique XOR Triplets I

作者：王一哲
日期：2026年7月23日


LeetCode 題目連結：3513. Number of Unique XOR Triplets I

解題想法

中等難度題。這題考數學，題目給一個長度為 $n$ 的陣列 $nums$，且 $nums$ 的內容為任意排列的 $1$ 到 $n$，可以從 $nums$ 之中任取 3 個數字求 XOR，數字可以重複，求總共有幾個計算結果。這題如果用 3 層迴圈硬算一定會超時，要找出數學關係後直接輸出答案。如果 $n = 1$，只有 1 個計算結果 1^1^1 = 1。如果 $n = 2$，只有 2 個計算結果，例如 01^01^01 = 01, 01^01^10 = 10。如果 $n = 3$，最大值為 001^001^111 = 111，不可能超過 $111_2 = 8$，計算結果在 $0$ 到 $2^n - 1$ 之間，答案等於 $2^n$。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 31.84 MB, beats 91.53%.

class Solution:
    def uniqueXorTriplets(self, nums: List[int]) -> int:
        n = len(nums)
        # 特例，n = 1，1位數，只有 1^1^1 = 1
        if n == 1: return 1
        # 特例，n = 2，2位數，只有 01^01^01 = 1, 01^01^10 = 2
        if n == 2: return 2
        # 一般狀況，n >= 3，最大值為 n 個 1，即 2**n - 1，共有 2**n 個答案
        bits = n.bit_length()
        return 1 << bits

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 198.80 MB, beats 85.00%.

class Solution {
public:
    int uniqueXorTriplets(vector<int>& nums) {
        unsigned int n = nums.size();
        // 特例，n = 1，1位數，只有 1^1^1 = 1
        if (n == 1) return 1;
        // 特例，n = 2，2位數，只有 01^01^01 = 1, 01^01^10 = 2
        if (n == 2) return 2;
        // 一般狀況，n >= 3，最大值為 n 個 1，即 2**n - 1，共有 2**n 個答案
        return 1 << bit_width(n);
    }
};