---
# System prepended metadata

title: 2997. Minimum Number of Operations to Make Array XOR Equal to K
tags: [C++, LeetCode]

---

# LeetCode 2997. Minimum Number of Operations to Make Array XOR Equal to K

https://leetcode.com/problems/minimum-number-of-operations-to-make-array-xor-equal-to-k/description/

## 題目大意

給一個整數陣列 `nums` 跟整數 `k` ，我們可以對 `nums` 中的任一數字反轉其二進制表示時的任意 bit

回傳我們最少用多少這樣的操作可以最終 `nums` 裡所有元素 XOR 後等於 `k` ？

## 思考

想法很簡單，如果我不知道現在的 `nums` 還缺多少上述操作後全部 XOR 會變 `k` ，那我先把現在的 `nums` 元素全部 `XOR` 再看看跟 `k` 還差多少個 bit 不同不就是所求嗎？

這題考的就是你對 XOR 本質是否熟悉

```cpp!
class Solution
{
public:
    int minOperations(vector<int> &nums, int k)
    {
        const int xorNums = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
        return __builtin_popcount(xorNums ^ k);
    }
};
```

`__builtin_popcount()` 會回傳該正整數在二進制表示下有多個 bits 是 `1`

我們知道 XOR 本質是找不同，所以跟`xorNums` 在二進制表示下與 `k` 不同的那些 bit 兩者 XOR 後會是 `1`

有關更多 `__builtin_popcount()` 歡迎參考下列文章

- [x] [C++ __builtin_popcount() Function](https://www.geeksforgeeks.org/cpp-__builtin_popcount-function/)

當然，你也可以像下面這樣寫，不過這寫法會多花空間存

```cpp!
class Solution
{
public:
    int minOperations(vector<int> &nums, int k)
    {
        const int xorNums = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
        return bitset<32>(xorNums ^ k).count();
    }
};
```

或是你手寫迴圈算也行，反正想法一樣

## 小補充

另外， `C++20` 後有個 [`std::popcount()`](https://en.cppreference.com/w/cpp/numeric/popcount)

也是得到一樣的結果
