数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法律研究通过对 C++ 数组中所有元素应用 XOR 运算来最小化数组和
描述
给定大小为 N 的数组。求一个元素 X，使得当对 X 与数组的每个元素执行 XOR 运算时，数组元素的和应该最小。
If input array is:
arr [] = {8, 5, 7, 6, 9}
then minimum sum will be 30
Binary representation of array elments are:
8 : 1000
5 : 0101
7 : 0111
6 : 0101
9 : 1001
If X = 5 then after performing XOR sum will be 30:
8 ^ 5 = 13
5 ^ 5 = 0
7 ^ 5 = 2
6 ^ 5 = 3
9 ^ 5 = 12
Sum = 30 (13 + 0 + 2 + 3 + 12)算法
1. Create a bitMap of size 32 as we are using 32 bit integer. 2. Iterate over an array and for each element of an array: a. If 0th bit of an element is set then increment count of bitMap[0] b. If 1st bit of an element is set then increment count of bitMap[1] and so on. 3. Now find X by iterating over bitMap array as follows: if bitMap[i] > n/2: then X = X + pow(2, i); 4. Iterate over input array. Perform XOR operation with X and each element of an array 5. Calculate sum of array elements
示例
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
const int MAX_SIZE = 32;
int getSum(int *arr, int n){
int bitMap[MAX_SIZE];
int bitLength = 0;
int sum = 0;
int res = 0;
fill(bitMap, bitMap + n, 0);
for (int i = 0; i < n; ++i) {
int num = arr[i];
int f = 0;
while (num > 0) {
int rem = num % 2;
num = num / 2;
if (rem == 1) {
bitMap[f]++;
}
++f;
bitLength = max(bitLength, f);
}
}
int candidate = 0;
for (int i = 0; i < bitLength; ++i) {
int num = pow(2, i);
if (bitMap[i] > n / 2) {
candidate += num;
}
}
for (int i = 0; i < n; ++i) {
sum += arr[i] ^ candidate;
}
return sum;
}
int main(){
int arr[] = {8, 5, 7, 6, 9};
cout << "Minimum sum: " << getSum(arr, SIZE(arr)) << "\n";
return 0;
}输出
当你编译并执行上述程序时，它会生成以下输出 −
Minimum sum: 30
更新于: 2019 年 10 月 23 日
177 次浏览
广告