在C ++中使数组XOR为零的最少操作

问题陈述

我们得到了n个元素的数组。任务是使整个数组的XOR为0。我们可以执行以下操作来实现此目的。

我们可以选择任何一个元素-

• 选择元素后，我们可以将其增加或减少1。

• 我们需要找到所选元素的最小增/减操作数，以使整个数组的XOR和为零

示例

如果arr [] = {2，4，7}，则需要1操作-

• 选择元素2

• 减1

• 现在，数组变为{3，4，7}，其XOR为0

算法

• 查找整个数组的异或

• 现在，假设我们选择了元素arr [i]，那么该元素所需的成本将是绝对的（arr [i]-（XORsum ^ arr [i]））

• 计算每个元素的这些绝对值的最小值将是我们的最低要求

示例

#include <iostream>
#include <climits>
#include <cmath>
using namespace std;
void getMinCost(int *arr, int n) {
   int operations = INT_MAX;
   int elem;
   int xorValue = 0;
   for (int i = 0; i < n; ++i) {
      xorValue = xorValue ^ arr[i];
   }
   for (int i = 0; i < n; ++i) {
      if (operations > abs((xorValue ^ arr[i]) - arr[i])) {
         operations = abs((xorValue ^ arr[i]) - arr[i]);
         elem = arr[i];
      }
   }
   cout << "Element= " << elem << endl;
   cout << "Minimum required operations = " << abs(operations) << endl;
}
int main() {
   int arr[] = {2, 4, 7};
   int n = sizeof(arr) / sizeof(arr[0]);
   getMinCost(arr, n);
   return 0;
}

输出结果

当您编译并执行上述程序时。它生成以下输出：

Element = 2
Minimum required operations = 1