C++ में XOR ऑपरेशन द्वारा सरणी योग न्यूनतम करें

समस्या विवरण

एक सरणी दी गई है, एक मान X ढूंढें जिससे प्रत्येक तत्व के साथ XOR करने के बाद सरणी का योग न्यूनतम हो।

उदाहरण: arr = {8, 5, 7, 6, 9}

यदि X = 5, तो XOR के बाद: 13, 0, 2, 3, 12 → योग = 30 (न्यूनतम)

एल्गोरिदम

1. 32-बिट बिटमैप बनाएं
2. प्रत्येक तत्व के सेट बिट्स गिनें
3. यदि किसी बिट पोजीशन पर सेट बिट्स > n/2 हैं, तो X में वह बिट सेट करें
4. X से सभी तत्वों का XOR करके न्यूनतम योग निकालें

उदाहरण कोड

#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] = {0};
    int bitLength = 0;
    
    for (int i = 0; i < n; ++i) {
        int num = arr[i];
        int f = 0;
        while (num > 0) {
            if (num % 2 == 1) bitMap[f]++;
            num /= 2;
            ++f;
            bitLength = max(bitLength, f);
        }
    }
    
    int candidate = 0;
    for (int i = 0; i < bitLength; ++i) {
        if (bitMap[i] > n / 2)
            candidate += pow(2, i);
    }
    
    int sum = 0;
    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