C++でXORの結果が奇数になるペアの数を数える方法

はじめに

整数型の配列が与えられ、その配列の要素から組み合わせられるペアのうち、XOR(排他的論理和)演算の結果が奇数になるペアの総数を求めるのが本記事の課題です。

XOR演算の真理値表

この真理値表から分かるように、XORの結果が「1」になるのは2つの値が異なる場合だけです。整数の最下位ビットに着目すると、偶数の最下位ビットは0、奇数の最下位ビットは1であるため、XORの結果が奇数になるのは「片方が偶数でもう片方が奇数」の組み合わせだけであることが分かります。したがって、答えは「偶数の個数 × 奇数の個数」で求められます。

入出力の例

入力 − int arr[] = {2, 8, 1, 5, 11}

出力 − XORが奇数になるペアの数:6

説明

配列 {2, 8, 1, 5, 11} に含まれるすべてのペアと、そのXORの結果は以下の通りです。

このうち結果が奇数になるのは (2,1)=3、(2,5)=7、(2,11)=9、(8,1)=9、(8,5)=13、(8,11)=3 の6ペアです。偶数が2個({2, 8})、奇数が3個({1, 5, 11})なので、2 × 3 = 6 という計算でも同じ結果が得られます。

プログラムのアプローチ

• ペアを作成する対象となる整数要素の配列を入力として受け取ります。
• 配列のサイズを計算し、そのデータを関数に渡して処理を行います。
• XORが奇数になるペアの数を格納するための一時変数 count を用意します。
• i を 0 から配列のサイズまで for ループで繰り返します。
• ループ内で、arr[i] % 2 == 0(偶数)であれば even_XOR を1増やし、そうでなければ odd_XOR を1増やします。
• count を「odd_XOR × even_XOR」として計算します。
• count を返します。
• 結果を出力します。

この方法なら、すべてのペアを総当たりで調べる O(n²) のアプローチと比べ、配列を一度走査するだけで済むため、時間計算量は O(n)、空間計算量は O(1) と非常に効率的です。

コード例

#include <iostream>
using namespace std;
//XORが奇数になるペアを数える
int Odd_XOR(int arr[], int size){
    int count = 0;
    int odd_XOR = 0;
    int even_XOR = 0;
    for (int i = 0; i < size; i++){
        if (arr[i] % 2 == 0){
            even_XOR++;
        }
        else{
            odd_XOR++;
        }
    }
    count = odd_XOR * even_XOR;
    return count;
}
int main(){
    int arr[] = { 2, 6, 1, 4 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"XORが奇数になるペアの数: "<<Odd_XOR(arr, size);
    return 0;
}

出力

上記のコードを実行すると、以下の出力が得られます。

XORが奇数になるペアの数: 3

まとめ

配列 {2, 6, 1, 4} の場合、偶数は {2, 6, 4} の3個、奇数は {1} の1個なので、XORが奇数になるペアの数は 3 × 1 = 3 となります。このように、偶数と奇数の個数をそれぞれ数えて掛け合わせるだけで答えが求まるのが、本アルゴリズム最大のポイントです。二重ループによる総当たり(O(n²))を避け、線形時間(O(n))で処理できるため、要素数が多い配列でも高速に動作します。