【C++】配列の全ペアの和からなる数列のXORを効率的に求める方法

問題概要

この問題では、n個の要素からなる配列が与えられます。配列Aのすべての要素同士のペア（自分自身とのペアも含む）の和を要素とする、サイズ n×n の数列Bを生成し、その数列に含まれるすべての要素のXOR（排他的論理和）を求めて出力するのが課題です。

入出力例

入力 − A = (1, 4, 5)

出力 − 0

説明 −

B (1+1, 1+4, 1+5, 4+1, 4+4, 4+5, 5+1, 5+4, 5+5)
B (2, 5, 6, 5, 8, 9, 6, 9, 10)
すべての値のXOR = 2^5^6^5^8^9^6^9^10 = 0

解法のアプローチ

この問題を効率的に解く鍵となるのは、XORの基本的な性質です。まず、「同じ値同士のXORは必ず0になる」（a ^ a = 0）という性質があります。

生成された配列Bをよく観察すると、a[i]+a[j] と a[j]+a[i] のように、順序が違うだけで同じ値になる要素が必ずペアで存在します。これらは互いに打ち消し合ってXORでは0になるため、最終的に残るのは対角成分にあたる「2×a[i]」という要素だけです。

つまり、元の配列Aの全要素のXORを一度計算し、その結果を2倍すれば答えが求まります。これにより、n×n個の要素を実際に生成することなく、O(n)の時間で解けるようになります。

実装例

上記のアルゴリズムを実装したプログラムは以下の通りです。

#include <iostream>
using namespace std;
int findSumXor(int arr[], int n){
    int XOR = 0;
    for (int i = 0; i < n; i++) {
        XOR = XOR ^ arr[i];
    }
    return XOR * 2;
}
int main(){
    int arr[3] = { 2, 4, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"配列の要素ペアの和のXORは\t"<<findSumXor(arr, n);
    return 0;
}

出力

配列の要素ペアの和のXORは 2

計算量について

この解法の時間計算量はO(n)、必要な追加メモリはO(1)です。素朴にn×n個のペアをすべて生成してXORを取る方法ではO(n²)の時間がかかりますが、XORの性質を活かすことで大幅に効率化できる点がこのアルゴリズムの魅力です。