LeetCode 解題筆記：3702. Longest Subsequence With Non-Zero Bitwise XOR

作者：王一哲
日期：2026年8月15日


LeetCode 題目連結：3702. Longest Subsequence With Non-Zero Bitwise XOR

解題想法

中等難度題。題目給一個整數陣列 $nums$，取任意長度的子陣列使其中所有的數字 XOR 不等於 0，求最大長度。這題看起來很像 0/1 背包問題，因為每個數字只有選或不選兩種可能性，但是這題的數字最大為 $10^9$，如果用 0/1 背包問題的方式處理會超時。這題需要用到 XOR 的數學性質，假設 $nums$ 的長度為 $n$，答案可能是以下 3 種狀況

1. 如果所有的數字取 XOR 的結果 $total$ 不為 $0$，直接回傳 $n$。
2. 如果 $total$ 為 $0$，且 $nums$ 之中有任意一個數字不為 $0$，刪除一個不為 $0$ 的數字可以使 $total$ 不為 $0$，回傳 $n-1$。
3. 如果 $total$ 為 $0$，且所有的數字為 $0$，回傳 $0$。

範例測資 2 就是狀況 2，$nums = [2, 3, 4] = [10_2, 11_2, 100_2]$，如果取 $[2, 3, 4]$ 計算 XOR $$ 10 \oplus 11 \oplus 100 = 1 \oplus 100 = 0 $$ 刪除任意一個數字再取 XOR $$ 10 \oplus 11 = 1 ~~~~~ 10 \oplus 100 = 110 ~~~~~ 11 \oplus 100 = 101 $$ 如果用數學證明狀況 2，可以用反證法。如果陣列 $a$ 所有的元素取 XOR 為 $0$ $$ a_0 \oplus a_1 \oplus a_2 \oplus \dots \oplus a_{n-1} = 0 $$ 假設移除其中一項不為 $0$ 的元素 $a_i$ 可以使 $a$ 所有的元素取 XOR 仍然為 $0$，因為 $a_i \oplus a_i = 0$，所以 $$ (a_0 \oplus a_1 \oplus a_2 \oplus \dots \oplus a_{n-1}) \oplus a_i = 0 ~\Rightarrow~ 0 \oplus a_i = 0 $$ 但是 $$ 0 \oplus a_i = a_i $$ 兩個結果互相矛盾，假設錯誤，移除其中一項不為 $0$ 的元素 $a_i$ 可以使 $a$ 所有的元素取 XOR 不為 $0$。

Python 程式碼

Runtime: 27 ms, beats 74.19%. Memory: 33.18 MB, beats 66.13%.

class Solution:
    def longestSubsequence(self, nums: List[int]) -> int:
        n = len(nums)  # 數量
        non_zero = False  # 是否有任意一個非 0 的數字
        # 先取所有數字的 XOR
        total = 0
        for num in nums:
            total ^= num
            if num > 0: non_zero = True
        # 狀況1，所有數字的 XOR 不等於 0
        if total > 0: return n
        # 狀況2，所有數字的 XOR 等於 0，至少有一個非 0 的數字
        if total == 0 and non_zero: return n-1
        # 狀況3，所有數字都是 0
        return 0

functools 函式庫當中有一個 reduce 函式，可以將指定的運算式套用在某個可以迭代的物件上，語法為

functools.reduce(運算式, 可迭代物件, 起始值)

其中起始值預設為 0。我們可以用 reduce 搭配 lambda function 對 $nums$ 所有的元素取 XOR。Runtime: 65 ms, beats 13.71%. Memory: 33.14 MB, beats 66.13%.

class Solution:
    def longestSubsequence(self, nums: List[int]) -> int:
        # 狀況3，全部都是 0
        if all(num == 0 for num in nums):
            return 0
        # 對所有的數字取 XOR
        total = functools.reduce(lambda x, y : x^y, nums, 0)
        # 狀況1，所有數字取 XOR 不等於 0
        if total > 0: return len(nums)
        # 狀況2，所有數字取 XOR 等於 0，有非 0 的數字
        return len(nums) - 1

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 171.35 MB, beats 22.70%.

class Solution {
public:
    int longestSubsequence(vector<int>& nums) {
        int n = (int)nums.size();  // 數量
        bool non_zero = false;  // 是否有任意一個非 0 的數字
        // 先取所有數字的 XOR
        int total = 0;
        for(int num : nums) {
            total ^= num;
            if (num > 0) non_zero = true;
        }
        // 狀況1，所有數字的 XOR 不等於 0
        if (total > 0) return n;
        // 狀況2，所有數字的 XOR 等於 0，至少有一個非 0 的數字
        if (total == 0 && non_zero) return n-1;
        // 狀況3，所有數字都是 0
        return 0;
    }
};

C 語言程式碼

Runtime: 0 ms, beats 100.00%. Memory: 22.65 MB, beats 33.33%.

int longestSubsequence(int* nums, int numsSize) {
    bool non_zero = false;  // 是否有任意一個非 0 的數字
    // 先取所有數字的 XOR
    int total = 0;
    for(int i = 0; i < numsSize; i++) {
        total ^= nums[i];
        if (nums[i] > 0) non_zero = true;
    }
    // 狀況1，所有數字的 XOR 不等於 0
    if (total > 0) return numsSize;
    // 狀況2，所有數字的 XOR 等於 0，至少有一個非 0 的數字
    if (total == 0 && non_zero) return numsSize - 1;
    // 狀況3，所有數字都是 0
    return 0;
}