Q3. Minimum Removals to Achieve Target XOR

📘 題目敘述

給你一個整數陣列 nums 和一個整數 target。

你可以從 nums 中移除任意多個元素（也可以一個都不移除）。

請回傳最少需要移除多少個元素，才能讓剩下元素的 bitwise XOR 恰好等於 target。

如果做不到，請回傳 -1。

空陣列的 XOR 定義為 0。

條件限制

• 1 <= nums.length <= 40
• 0 <= nums[i] <= 10^4
• 0 <= target <= 10^4

🧠 解題思路

這題表面上是在問「最少刪掉幾個」，但我換個角度想會比較自然：

我其實是在找，最多能保留幾個元素，讓這些保留下來的元素 XOR 剛好等於 target。

因為如果我能保留的最多元素數量是 k，那最少刪除數量就是：

• nums.size() - k

所以我這份做法是用 DP 去記：

• 某個 XOR 值能不能做到
• 如果能做到，最多可以保留幾個元素

然後我一個一個處理 nums 裡的數字，決定要不要把它選進來。

如果把它選進來，XOR 會從 x 變成 x ^ i，而保留元素數量就會多 1。

最後只要看：

• dp[target]

如果它還是無法達成，就回傳 -1；

如果可以達成，就回傳總長度減掉最多保留數量。

所有變數

• M：DP 狀態範圍上限，這份程式設成 16384
• dp：dp[x] 表示 XOR 值為 x 時，最多可以保留幾個元素；如果做不到則為 -1
• ndp：這一輪更新用的暫存 DP

🪜 主要流程步驟

1. 先定義 DP 的意義

const int M = 16384;
vector<int> dp(M, -1);
dp[0] = 0;

我這裡把 dp[x] 定義成：

• XOR 恰好等於 x 時
• 最多可以保留幾個元素

如果某個 XOR 值目前做不到，就記成 -1。

一開始什麼都不選時：

• XOR = 0
• 保留元素數量 = 0

所以：

dp[0] = 0;

這就是整個 DP 的起點。

2. 依序處理 nums 裡的每個元素

for (int i : nums) {
    vector<int> ndp = dp;

這裡我一個一個看 nums 裡的數字 i。

每次都先複製一份 dp 到 ndp，意思是：

• 如果這輪我不選 i
• 那原本能做到的狀態還是保留

所以 ndp = dp 代表「不選這個數字」的情況先全部繼承下來。

3. 嘗試把目前這個數字選進來

for (int x = 0; x < M; x++) {
    if (ndp[x] != -1) {
        ndp[x ^ i] = max(ndp[x ^ i], dp[x] + 1);
    }
}

這裡的想法是：

如果原本 XOR = x 這個狀態做得到，

那我把目前數字 i 選進來之後，新的 XOR 就會變成：

• x ^ i

而且保留元素數量會變成：

• dp[x] + 1

所以我就更新：

• ndp[x ^ i]

代表「做到這個新 XOR 值時，最多能保留幾個元素」。

4. 這裡為什麼要用 dp[x] 而不是 ndp[x]

更新時你寫的是：

ndp[x ^ i] = max(ndp[x ^ i], dp[x] + 1);

不是用 ndp[x] + 1。

這很重要，因為我希望：

• 每個元素 i 這一輪最多只能被使用一次

如果我用 ndp[x] 去更新，可能就會把同一輪剛更新出來的結果再拿來繼續轉移，等於同一個數字被重複選很多次。

所以這裡一定要從「上一輪的 dp」轉移到「這一輪的 ndp」，這樣才是正確的 0/1 選或不選。

5. 每輪更新完後，把結果存回 dp

dp = ndp;

當前這個數字 i 的所有轉移都做完後，

就把這一輪的新結果正式存回 dp，讓下一個數字繼續接著做。

6. 最後看 target 能不能做到

return dp[target] < 0 ? -1 : nums.size() - dp[target];

最後我只要檢查：

• dp[target]

如果它還是小於 0，表示 XOR 做不到 target，那答案就是 -1。

如果做得到，dp[target] 表示：

• XOR 等於 target 時
• 最多能保留多少元素

而題目要的是最少刪除數量，所以答案就是：

• nums.size() - dp[target]

7. 為什麼這樣就等於最少移除數量

因為每個元素只有兩種選擇：

• 保留
• 移除

而總元素數固定。

所以：

• 最少移除數量
• 等價於最多保留數量

只要我找出「XOR 剛好等於 target 時最多能保留幾個元素」，

最後用總長度去減，就自然得到最少刪除數量。

⏱️ 複雜度

設 n = nums.length。

• 時間複雜度：O(nM)

其中 M = 16384，每個元素都會掃過所有 XOR 狀態一次。

• 空間複雜度：O(M)

使用了 dp 和 ndp 兩個長度為 M 的陣列。

💻 程式碼實作

class Solution {
public:
    int minRemovals(vector<int>& nums, int target) {
        const int M = 16384;
        vector<int> dp(M, -1);
        dp[0] = 0;
        for (int i : nums) {
            vector<int> ndp = dp;
            for (int x = 0; x < M; x++) {
                if (ndp[x] != -1) {
                    ndp[x ^ i] = max(ndp[x ^ i], dp[x] + 1);
                }
            }
            dp = ndp;
        }

        return dp[target] < 0 ? -1 : nums.size() - dp[target];
    }
};

🔗 題目連結

https://leetcode.com/contest/weekly-contest-494/problems/minimum-removals-to-achieve-target-xor/