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
以上是 C ++中所有子数组的XOR之和 的全部内容， 来源链接： utcz.com/z/343325.html
