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

在这个问题中，我们得到了n个元素的数组。我们的任务是打印从数组元素创建的所有可能的子数组（按顺序进行）的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)

为了解决这个问题，一个简单的解决方案是遍历所有子数组并找到xor。但这是一种低效的方法。更好的方法可能是计算出现在所有子数组中的数组每个元素的频率，并使用元素xor- xor的属性，即使次数为0。使用此方法，我们将忽略子数组列表中出现偶数次的所有值，现在考虑具有奇数出现频率的元素，即，具有奇数出现频率的元素的异或将给出最终结果。

为了找到数组的每个元素在其子数组中的出现，我们将使用以下公式（i + 1）*(ni)。

使用该公式，我们将找到每个元素的出现频率，然后考虑那些具有奇数频率的元素，然后进行异或运算以获得最终结果。

示例

展示我们解决方案实施情况的程序，

#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