C++で配列のXORをゼロにするための最小演算

問題の説明

n個の要素の配列が与えられます。タスクは、配列全体のXORを0にすることです。これを実現するには、次のようにします。

要素のいずれかを選択できます-

• 要素を選択した後、要素を1ずつインクリメントまたはデクリメントできます。
• 配列全体のXOR合計をゼロにするために、選択した要素に必要なインクリメント/デクリメント操作の最小数を見つける必要があります

例

arr [] ={2、4、7}の場合、1回の操作が必要です-

• 要素2を選択
• 1つ減らします
• 配列は{3、4、7}になり、そのXORは0になります

アルゴリズム

• アレイ全体のXORを見つける
• ここで、要素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