C++で指定されたXOR値を持つペアの数を効率的にカウントする方法

このチュートリアルでは、配列の中から指定されたXOR値を持つペアの数を求めるプログラムについて解説します。

具体的には、整数の配列とターゲットとなる値が与えられ、その2つの要素のXOR（排他的論理和）がターゲット値と一致するペアがいくつ存在するかをカウントするのが課題です。

アルゴリズムの考え方

全てのペアを総当たりで調べる方法（O(n²)）もありますが、ここではハッシュマップ（unordered_map）を活用することで、時間計算量O(n)で効率的に解く手法を紹介します。

基本的なアイデアは以下の通りです。

• XORの性質を利用します。ある要素 a に対して「a ^ b = x」が成り立つとき、「b = x ^ a」と変形できます。
• 配列を走査しながら、各要素に対して「x ^ 現在の要素」がすでに登場しているかをハッシュマップで確認します。
• 登場していれば、その出現回数だけペアが成立するため、結果に加算します。
• 重複した値にも正しく対応できるよう、各要素の出現回数をマップに記録していきます。

C++での実装例

#include<bits/stdc++.h>
using namespace std;

// XORが指定された値と等しいペアの数を返す関数
int count_pair(int arr[], int n, int x){
    int result = 0;
    // 重複した値に対応するためハッシュマップを使用
    unordered_map<int, int> m;
    for (int i=0; i<n ; i++){
        int curr_xor = x^arr[i];
        if (m.find(curr_xor) != m.end())
            result += m[curr_xor];
        m[arr[i]]++;
    }
    return result;
}

int main(){
    int arr[] = {2, 5, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x = 0;
    cout << "指定されたXORを持つペアの数 = " << count_pair(arr, n, x);
    return 0;
}

実行結果

指定されたXORを持つペアの数 = 1

コードの解説

この例では、配列 {2, 5, 2} からXORが 0 になるペアを探しています。「2 ^ 2 = 0」が成立するため、同じ値 2 を持つ2つの要素が1組のペアとしてカウントされ、結果は 1 となります。

ループ内の処理の流れは次の通りです。

1. 現在の要素 arr[i] に対し、必要な相手の値 x ^ arr[i] を計算します。
2. その値がすでにマップに存在すれば、これまでに出現した回数分だけペアが成立するので result に加算します。
3. 最後に現在の要素の出現回数をマップに記録します。

この手法により、二重ループを使わずに線形時間でペアを数えられるため、大規模な配列でも高速に動作します。