数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中查找与数组中每个整数进行异或运算时，能得到最小和的数字
概念
对于给定的非负整数数组 Arr[]，任务是确定一个整数 X，使得 (Arr[0] XOR X) + (Arr[1] XOR X) + … + Arr[n – 1] XOR X 的结果尽可能小。
输入
Arr[] = {3, 4, 5, 6, 7}输出
X = 7, Sum = 10
方法
因此，我们将验证数组中每个数字在二进制表示中的第 i 位，并考虑并统计那些第 i 位设置为 '1' 的数字，因为这些设置的位将有助于最大化总和而不是最小化。因此，如果计数大于 N/2，我们必须将此设置的第 i 位构建为 '0'；如果计数小于 N/2，则具有第 i 位设置的数字较少，因此不会影响答案。我们知道根据两个位上的异或运算，当 A XOR B 且 A 和 B 都相同时，它会产生 '0' 的结果，因此我们将在此数字 (num) 中构建该第 i 位为 '1'，因此 (1 XOR 1) 将给出 '0' 并最小化总和。
示例
// C++ implementation of the approach
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
void findX1(int arr1[], int n1){
int* itr1 = max_element(arr1, arr1 + n1);
int p1 = log2(*itr1) + 1;
int X1 = 0;
for (int i = 0; i < p1; i++) {
int count1 = 0;
for (int j = 0; j < n1; j++) {
if (arr1[j] & (1 << i)) {
count1++;
}
}
if (count1 > (n1 / 2)) {
X1 += 1 << i;
}
}
long long int sum1 = 0;
for (int i = 0; i < n1; i++)
sum1 += (X1 ^ arr1[i]);
cout << "X = " << X1 << ", Sum = " << sum1;
}
// Driver code
int main(){
int arr1[] = { 3, 4, 5, 6, 7 };
int n1 = sizeof(arr1) / sizeof(arr1[0]);
findX1(arr1, n1);
return 0;
}输出
X = 7, Sum = 10
更新于: 2020-07-23
210 次浏览
广告