C++でXORが0になる配列内のペアの数を求める方法

n個の要素を含む配列が与えられたとき、XOR(排他的論理和)の計算結果が0になるペアの数を求めることを考えます。ペア(x, y)のXORが0になるのは、x = y が成り立つ場合、すなわち2つの値が等しいときだけです。これは「同じ数値同士のXORは必ず0になる」というビット演算の基本的な性質によるものです。

解法のアプローチ

この問題は、次の手順で解くことができます。

1. まず、配列を昇順にソートします。
2. ソート後は同じ値どうしが隣り合って並ぶため、連続する2つの要素を比較し、等しければカウントを1つ増やします。
3. すべての要素が同じ値である場合、末尾側のペアがカウントから漏れる可能性があります。そこで、配列の先頭と末尾の要素が等しいかどうかを確認し、等しければカウントをさらに1つ増やします。

サンプルコード

#include<iostream>
#include<algorithm>
using namespace std;
int countPairs(int arr[], int n) {
    int count = 0;
    sort(arr, arr+n);
    for(int i = 0; i<n - 1; i++){
        if(arr[i] == arr[i+1]){
            count++;
        }
    }
    if(arr[0] == arr[n-1])
        count++;
    return count;
}
int main() {
    int arr[] = {1, 2, 1, 2, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Number of pairs: " << countPairs(arr, n);
}

実行結果

Number of pairs: 2

コードの解説

サンプル配列 {1, 2, 1, 2, 4} をソートすると {1, 1, 2, 2, 4} になります。隣接する要素を順に比較すると、「1と1」「2と2」の2組が等しいため、カウントは2になります。先頭と末尾の要素(1と4)は異なるため、追加のカウントは発生せず、最終的な出力は「Number of pairs: 2」となります。

補足: すべての組み合わせを正確に数えたい場合

上記の方法は、隣接する等しい要素のペアを数えるアプローチです。同じ値が3回以上出現するケースで、すべてのペアの組み合わせ(同じ値がk個あるとき、選び方は k×(k-1)/2 通り)を正確に求めたい場合は、ハッシュマップなどで各値の出現回数を集計し、k×(k-1)/2 を合計する方法が確実です。この方法ならソートが不要となり、計算量をO(n)に抑えることができます。