C++のすべてのサブアレイXORのXOR

この問題では、n個の要素の配列が与えられます。私たちのタスクは、XORのXORを、配列の要素から作成されたすべての可能なサブ配列（順番に取得）を出力することです。

問題を理解するために例を見てみましょう

入力 −配列={1、3、6、8}

出力 − 0

説明 −

(1) ^ (3) ^ (6) ^ (8) ^ (1^3) ^ (3^6)^ (6^8) ^ (1^3^6) ^ (3^6^8) ^ (1^3^6^8)

この問題を解決するための簡単な解決策は、すべてのサブアレイを反復処理してxorsを見つけることです。しかし、これは非効率的なアプローチです。より良いアプローチは、すべてのサブ配列で発生した配列の各要素の頻度をカウントし、要素のxor −xorのプロパティを偶数回使用することです。 。これを使用して、サブ配列リストで偶数回出現するすべての値を無視します。これで、出現頻度が奇数の要素が考慮されます。つまり、出現頻度が奇数の要素のxorが最終結果になります。

サブ配列内の配列の各要素の出現を見つけるために、この式を使用します（i + 1）*（n-i） 。

この式を使用して、各要素の出現頻度を見つけ、次に、奇数の頻度を持つ要素を検討し、xまたはそれから最終結果を取得します。

例

ソリューションの実装を示すプログラム

#include <iostream>
using namespace std;
   int xorSubarrayXors(int arr[], int N){
   int result = 0;
   for (int i = 0; i < N; i++){
      int freqency = (i + 1) * (N - i);
      if (freqency % 2 == 1)
         result ^= arr[i];
   }
   return result;
}
int main() {
   int arr[] = {1, 3, 6, 8};
   int N = sizeof(arr) / sizeof(arr[0]);
   cout<<"The xor of all subarray xors is : "<<xorSubarrayXors(arr, N);
   return 0;
}

出力

The xor of all subarray xors is : 0