C++のすべてのサブ配列のXORの合計

この問題では、n個の数の配列arr[]が与えられます。私たちのタスクは、配列のすべてのサブ配列のXORの合計を見つけるプログラムを作成することです。

ここでは、指定された配列のすべてのサブ配列を検索する必要があります。次に、各サブ配列について、要素のxorを検索し、XOR値を合計変数に追加します。

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

Input: arr[] = {5, 1, 4}
Output:
Explanation: XOR of all subarrays for the array :
XOR {5} = 5
XOR {1} = 1
XOR {4} = 4
XOR {5,1} = 5^1 = 4
XOR {1, 4} = 1^4 = 5
XOR {5, 1, 4} = 5^1^4 = 0
Sum = 5 + 1 + 4 + 4 + 5 + 0 = 19

この問題を解決する簡単な方法は、次のforループを使用してすべてのサブ配列を見つけることです。次に、サブ配列の要素のXORを見つけて、合計変数に追加します。

このソリューションは、ループのネストを使用するため効率的ではなく、時間計算量が指数関数的に複雑になります。

この問題を解決するための効率的なアプローチは、プレフィックス配列を使用することです。このプレフィックス配列は、iまで配列のすべての要素のxorを格納します。つまり、

prefixarr[i] = arr[0]^arr[1]^ … ^arr[i].

この後、簡単な式を適用して、インデックスiからjまでの要素のXORを見つけることができます。

XOR(i-j) = prefixarr[j] - prefixarr[i]for i >= 0.
If i = 0, XOR(i-j) = prefixarr[j]

この式を使用して、すべてのサブアレイのXORを見つけます。

例

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;
int calcSubArrayXORSum(int arr[], int n) {
   int sum = 0;
   int multiplier = 1;
   for (int i = 0; i < 30; i++) {
      int oddCount = 0;
      bool isOdd = 0;
      for (int j = 0; j < n; j++) {
         if ((arr[j] & (1 << i)) > 0)
            isOdd = (!isOdd);
         if (isOdd)
            oddCount++;
      }
      for (int j = 0; j < n; j++) {
         sum += (multiplier * oddCount);
         if ((arr[j] & (1 << i)) > 0)
            oddCount = (n - j - oddCount);
      }
      multiplier *= 2;
   }
   return sum;
}
int main() {
   int arr[] = { 3, 8, 13 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"Sum of XOR of all subarrays is "<<calcSubArrayXORSum(arr, n);
   return 0;
}

出力

Sum of XOR of all subarrays is 46