C++ 中所有子数组的异或和

在这个问题中，我们给定一个包含 n 个数字的数组 arr[]。我们的任务是创建一个程序来找到数组所有子数组的异或和。

这里，我们需要找到给定数组的所有子数组，然后对于每个子数组，我们将找到元素的异或并将其添加到 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

解决此问题的一个简单方法是使用下一个 for 循环来查找所有子数组。然后找到子数组元素的异或并将其添加到 sum 变量中。

此解决方案效率不高，因为它使用了循环嵌套并且将具有指数时间复杂度。

解决此问题的一个有效方法是使用前缀数组。此前缀数组将存储数组中所有元素到 i 的异或。即，

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

之后，我们可以应用一个简单的公式来查找从索引 i 到 j 的元素的异或。

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

使用此公式，我们将找到所有子数组的异或。

示例

程序说明我们解决方案的工作原理，

 在线演示

#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

sudhir sharma

更新于: 2020-08-17

755 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习