सी ++ में सरणी के सभी तत्वों पर एक्सओआर ऑपरेशन लागू करके सरणी योग को कम करना

विवरण

आकार की एक सरणी को देखते हुए, एन। एक तत्व एक्स खोजें जैसे कि सरणी तत्वों का योग न्यूनतम होना चाहिए जब एक्सओआर ऑपरेशन एक्स और सरणी के प्रत्येक तत्व के साथ किया जाता है।

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