C++で配列内のすべてのペアの和のXORを計算する方法

問題の概要

この問題では、サイズnの配列arr[]が与えられます。私たちのタスクは、配列内のすべてのペアについて要素の和を求め、それらの和のXORを計算するプログラムを作成することです。

例で問題を理解しましょう

入力: arr[] = {5, 7, 9}

出力: 22

説明:

(5+5) ^ (5+7) ^ (5+9) ^ (7+5) ^ (7+7) ^ (7+9) ^ (9+5) ^ (9+7) ^ (9+9) = 22

解法1: 単純なアプローチ（ネストしたループ）

最もシンプルな解法は、ネストしたループを使用して配列からすべての可能なペアを生成し、各ペアの和のXORを順に計算していく方法です。

アルゴリズム

XorSumを0で初期化します。

ステップ1: iを0からn-1まで繰り返します。

ステップ1.1: jを0からn-1まで繰り返します。

ステップ1.1.1: XorSumを更新します。すなわち、XorSum = XorSum ^ (arr[i]+arr[j])。

ステップ2: XorSumを返します。

コード例

#include <iostream>
using namespace std;

int findSumXORPair(int arr[], int n) {

    int XorSum = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            XorSum = XorSum^(arr[i]+arr[j]);
    return XorSum;
}

int main() {

    int arr[] = {5, 7, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"配列内の全ペアの和のXOR: "<<findSumXORPair(arr, n);
    return 0;
}

出力

配列内の全ペアの和のXOR: 22

この解法は時間計算量がO(n²)となるため、大きな配列を扱う場合には非効率です。

解法2: 効率的なアプローチ（XORの性質を利用）

より効率的な解法は、XORの性質を利用することです。ペア(i, j)と(j, i)の和は等しいため、XOR演算では互いに打ち消し合います。その結果、実際に残るのは(i, i)のペア、すなわち2×arr[i]だけとなります。したがって、配列内のすべての要素のXORを計算し、それを2倍すれば答えが求まります。

アルゴリズム

XorSumを0で初期化します。

ステップ1: iを0からn-1まで繰り返します。

ステップ1.1: XorSumを更新します。すなわち、XorSum = XorSum ^ arr[i]。

ステップ2: XorSumを2倍して返します。

コード例

#include <iostream>
using namespace std;

int findSumXORPair(int arr[], int n) {

    int XorSum = 0;
    for (int i = 0; i < n; i++)
        XorSum = XorSum^arr[i];
    XorSum = 2*XorSum;
    return XorSum;
}

int main() {

    int arr[] = {5, 7, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"配列内の全ペアの和のXOR: "<<findSumXORPair(arr, n);
    return 0;
}

出力

配列内の全ペアの和のXOR: 22

まとめ

ネストしたループによる単純な解法はO(n²)の時間計算量が必要ですが、XORの性質（同じ値同士のXORは0になる）を活用すれば、O(n)で答えを求めることができます。配列のサイズが大きい場合は、効率的な解法を選ぶことが重要です。