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