C++-এ অ্যারের সব উপাদানে XOR অপারেশন প্রয়োগ করে অ্যারে যোগফল ন্যূনীকরণ

বিবরণ

একটি N আকারের অ্যারে দেওয়া আছে। একটি উপাদান X খুঁজে বের করতে হবে যাতে অ্যারের সব উপাদানের সাথে XOR অপারেশন করার পর অ্যারে উপাদানগুলোর যোগফল ন্যূনতম হয়।

যদি ইনপুট অ্যারে: arr[] = {8, 5, 7, 6, 9} তবে ন্যূনতম যোগফল হবে 30
অ্যারে এলিমেন্টের বাইনারি রিপ্রেজেন্টেশন:
8 : 1000
5 : 0101
7 : 0111
6 : 0110
9 : 1001
যদি X = 5 হয় তবে XOR করার পর যোগফল 30:
8 ^ 5 = 13
5 ^ 5 = 0
7 ^ 5 = 2
6 ^ 5 = 3
9 ^ 5 = 12
Sum = 30 (13 + 0 + 2 + 3 + 12)

অ্যালগরিদম

1. ৩২ সাইজের একটি bitMap তৈরি করুন (৩২-বিট ইন্টিজার ব্যবহার করছি)।
2. অ্যারে 위로 ইটারেট করুন এবং প্রতিটি উপাদানের জন্য:
   a. যদি উপাদানের ০th বিট সেট থাকে, bitMap[0] এর কাউন্ট বাড়ান
   b. যদি ১st বিট সেট থাকে, bitMap[1] এর কাউন্ট বাড়ান,如此類推।
3. এখন bitMap অ্যারে 위로 ইটারেট করে X বের করুন:
   if bitMap[i] > n/2: তবে X = X + pow(2, i);
4. ইনপুট অ্যারে 위로 ইটারেট করুন। X এবং অ্যারের প্রতিটি উপাদানের সাথে XOR অপারেশন করুন।
5. অ্যারে উপাদানগুলোর যোগফল বের করুন।

উদাহরণ কোড

#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