C++でバイナリ文字列から1つの要素を削除してXORをゼロにする方法

問題の概要

この問題では、0と1だけで構成されたバイナリ文字列が与えられます。求めたいのは、1つの要素を削除したときに文字列全体のXORがゼロになるような削除方法の総数です。

まずは具体例で問題を確認してみましょう。

入力例

n = 11010

出力例

3

入力文字列「11010」には「1」が3つ含まれています。このうちどれか1つの「1」を削除すると、残る「1」は2個（偶数）となり、全体のXORが0になります。削除できるのは「1」の位置が3か所なので、答えは3通りです。

解法の考え方

この問題を解くカギは、XOR演算の基本的な性質にあります。

• 偶数個の「1」に対してXORを取ると、結果は必ず0になる
• 奇数個の「1」に対してXORを取ると、結果は1になる
• 「0」はXORの結果にまったく影響しない

これらの性質から、次のルールが導けます。

• 「1」の個数が偶数の場合：文字列全体のXORはすでに0です。ここから任意の「0」を1つ削除してもXORは変わらないため、答えは「0」の個数になります。
• 「1」の個数が奇数の場合：「1」を1つ削除すると残りの「1」が偶数個になり、XORが0になるため、答えは「1」の個数になります。

つまり、文字列を一度走査して「1」と「0」の個数を数えるだけで答えが求まります。

C++による実装

上記のロジックを実装したプログラムが以下のとおりです。

#include<iostream>
#include<string>
using namespace std;

int wayXorZero(string binaryString){
   int oneCount = 0, zeroCount = 0;
   int n = binaryString.length();

   // 「1」と「0」の個数をそれぞれカウント
   for (int i = 0; i < n; i++) {
       if (binaryString[i] == '1')
           oneCount++;
       else
           zeroCount++;
   }

   // 「1」が偶数個なら「0」の個数、奇数個なら「1」の個数を返す
   if (oneCount % 2 == 0)
       return zeroCount;
   return oneCount;
}

int main(){
   string binaryString = "10110100";
   cout<<"XORをゼロにする方法の数："<<wayXorZero(binaryString);
   return 0;
}

実行結果

XORをゼロにする方法の数：4

入力文字列「10110100」には「1」が4個（偶数）、「0」が4個含まれています。「1」の個数が偶数のため、XORを0のまま保てるのは「0」を削除する4か所であり、出力は4となります。

コードの解説

関数 wayXorZero() の処理の流れは次のとおりです。

1. 文字列を先頭から順に走査し、「1」の個数（oneCount）と「0」の個数（zeroCount）をカウントします。
2. 「1」の個数が偶数であれば、XORはすでに0になっているため「0」の個数を返します。
3. 「1」の個数が奇数であれば、「1」の個数をそのまま返します。

計算量

• 時間計算量：O(n) ― 文字列を1回だけ走査します（nは文字列の長さ）。
• 空間計算量：O(1) ― カウンタ用の整数変数2つのみを使用します。

まとめ

バイナリ文字列から1つの要素を削除してXORをゼロにする問題は、「1」の出現回数の偶奇に着目することが重要です。「1」が偶数個なら答えは「0」の個数、奇数個なら答えは「1」の個数というシンプルなルールにより、O(n)の線形時間で効率的に解くことができます。