C++で配列全体のXORを0にするための最小操作回数を求めるアルゴリズム

問題文

n個の要素からなる配列が与えられます。この問題の目標は、配列全体のXORを0にすることです。そのために、次のような操作を行うことができます。

まず、配列から任意の1つの要素を選択します。

• 要素を選択した後、その要素を1増やす（インクリメント）か、1減らす（デクリメント）ことができます。
• 配列全体のXORの合計を0にするために、選択した要素に対して必要な増減操作の最小回数を求めます。

例

arr[] = {2, 4, 7} の場合、必要な操作は1回だけです。

• 要素「2」を選択します。
• これを1増やします。
• 配列は {3, 4, 7} となり、そのXORは 3 ^ 4 ^ 7 = 0 になります。

アルゴリズム

この問題は、XORの性質を利用して効率的に解くことができます。

• まず、配列全体のXOR値を求めます。
• 要素 arr[i] を選択した場合、その要素を変更してXOR全体を0にするには、残りの要素のXOR（XORsum ^ arr[i]）に一致させればよいため、必要なコストは abs(arr[i] − (XORsum ^ arr[i])) となります。
• 各要素についてこの絶対値を計算し、その中で最小の値が答えとなります。

計算例

配列 {2, 4, 7} の場合、全体のXORは 2 ^ 4 ^ 7 = 1 です。要素「2」を選んだとき、目標値は 1 ^ 2 = 3 となり、必要な操作回数は |2 − 3| = 1 回です。他の要素を選んでもコストは1以上になるため、最小操作回数は1回となります。

C++での実装例

#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;
}

コードの解説

• 最初のループでは、配列全体のXOR値（xorValue）を計算しています。
• 2番目のループでは、各要素について「その要素を除外した残りのXOR（xorValue ^ arr[i]）」との差の絶対値、つまり必要な増減幅を求めています。
• 最も小さい増減幅を持つ要素とその操作回数を出力します。

このアルゴリズムの時間計算量はO(n)、空間計算量はO(1)であり、非常に効率的です。

出力

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Element = 2
Minimum required operations = 1