C ++の配列のすべての要素にXOR演算を適用して、配列の合計を最小化する

説明

サイズの配列が与えられた場合、N。Xと配列の各要素を使用してXOR演算を実行するときに、配列要素の合計が最小になるように要素Xを見つけます。

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