C ++中所有子数组的XOR之和

在这个问题中，我们得到了n个数字的数组arr []。我们的任务是创建一个程序，以查找该数组所有子数组的XOR之和。

在这里，我们需要找到给定数组的所有子数组，然后对于每个子数组，我们将找到element的xor并将XOR值添加到sum变量。

让我们举个例子来了解这个问题，

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

解决此问题的一种简单方法是使用next for循环查找所有子数组。然后找到子数组元素的XOR并添加到sum变量中。

该解决方案效率很高，因为它使用循环嵌套，并且时间复杂度呈指数级增长。

解决此问题的有效方法是使用前缀数组。此前缀数组将存储该数组所有元素的异或，直到iie，

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