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

この問題の簡単な解決策は、ネストされたループを使用することです。そして、配列からすべての可能なペアを作成します。そして、各ペアの合計のXORを計算します。

アルゴリズム：

XorSumを初期化します =0

ステップ1： 0からnまで繰り返します。フォロー：

ステップ1.1： 0からnまで繰り返します。フォローする

ステップ1.1.1： XorSumを更新します つまり、 XorSum =XorSum ^（arr [i] + arr [j]）。

ステップ2： 合計を返す

コードの動作を説明するプログラム

例

#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 of sum of all pairs in an array is "<<findSumXORPair(arr, n);
   return 0;
}

出力

XOR of sum of all pairs in an array is 22

このソリューションは、時間計算量がn ² のオーダーであるため、効率的ではありません。 。

効率的な解決策は、XORのプロパティを使用することです。この問題を解決するために、配列のすべての要素のXORを計算してから、2を掛けます。

アルゴリズム：

XorSum=0を初期化します

ステップ1： 0からnまで繰り返します。

ステップ1.1： XorSumを更新します。つまり、XorSum =XorSum ^ arr [i]

ステップ2： 合計を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 of sum of all pairs in an array is "<<findSumXORPair(arr, n);
   return 0;
}

出力

XOR of sum of all pairs in an array is 22