C ++中数组中所有对的总和的XOR之和
在这个问题中,我们得到了大小为n的数组arr []。我们的任务是创建一个程序,以查找数组中所有对之和的XOR之和。
让我们看一个例子来了解这个问题,
输入: arr [5、7、9]
输出: 22
解释:
(5 + 5)^(5 + 7)^(5 + 9)^(7 + 5)^(7 + 7)^(7 + 9)^(9 + 5)^(9 + 7)^(9 +9) = 22
解决此问题的简单方法是使用嵌套循环。并从数组中创建所有可能的对。并计算每对总和的异或。
算法:
初始化XorSum = 0
步骤1: 从0迭代到n。跟随:
步骤1.1: 从0迭代到n。跟随
步骤1.1.1: 更新XorSum,即XorSum = XorSum ^(arr [i] + arr [j])。
步骤2: 返回总和
用来说明我们代码工作方式的程序
示例
#include <iostream>输出结果using namespace std;
int findSumXORPair(int arr[], int n) {
int XorSum = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
XorSum = XorSum^(arr[i]+arr[j]);
return XorSum;
}
int main() {
int arr[] = {5, 7, 9};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"数组中所有对之和的异或为 "<<findSumXORPair(arr, n);
return 0;
}
数组中所有对之和的异或为 22
该解决方案效率不高,因为其时间复杂度约为n 2。
一个有效的解决方案是使用XOR的属性。为了解决该问题,我们将计算数组所有元素的XOR,然后将其乘以2。
算法:
初始化XorSum = 0
步骤1: 从0迭代到n。
步骤1.1: 更新XorSum,即XorSum = XorSum ^ arr [i]
第2步: 将总和加倍并返回。
该程序说明了我们解决方案的工作原理,
示例
#include <iostream>输出结果using namespace std;
int findSumXORPair(int arr[], int n) {
int XorSum = 0;
for (int i = 0; i < n; i++)
XorSum = XorSum^arr[i];
XorSum = 2*XorSum;
return XorSum;
}
int main() {
int arr[] = {5, 7, 9};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"数组中所有对之和的异或为 "<<findSumXORPair(arr, n);
return 0;
}
数组中所有对之和的异或为 22
以上是 C ++中数组中所有对的总和的XOR之和 的全部内容, 来源链接: utcz.com/z/320063.html