数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中所有子数组 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)
为了解决这个问题，一个简单的解决方案可能是遍历所有子数组并找到异或。但这是一种低效的方法。更好的方法可能是计算数组中每个元素在所有子数组中出现的频率，并使用异或的性质 - *元素异或偶数次的结果为 0*。利用这一点，我们将忽略在子数组列表中出现偶数次的的所有值，现在需要考虑出现频率为奇数的元素，即出现频率为奇数的元素的异或将给出最终结果。
为了找到数组中每个元素在其子数组中的出现次数，我们将使用此公式 (i+1)*(n-i)。
使用此公式，我们将找到每个元素出现的频率，然后考虑那些具有奇数频率的元素，异或它们以获得最终结果。
示例
程序展示了我们解决方案的实现，
#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
更新于: 2020年4月20日
392 次查看
广告