Tối thiểu hóa tổng mảng bằng phép XOR C++

Đề bài

Cho mảng size N. Tìm X sao cho tổng các phần tử sau khi XOR với X là nhỏ nhất.

Ví dụ: arr = {8, 5, 7, 6, 9}. X = 5 cho tổng nhỏ nhất = 30. 8^5=13, 5^5=0, 7^5=2, 6^5=3, 9^5=12. Tổng = 30.

Giải thuật

1. Tạo bitMap[32] đếm số bit 1 tại mỗi vị trí
2. Duyệt mảng, cập nhật bitMap
3. Xây dựng X: nếu bitMap[i] > n/2 thì set bit i của X = 1
4. Tính tổng: Σ(arr[i] ^ X)

Ví dụ minh họa

#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], f = 0;
        while (num > 0) {
            if (num % 2) 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 << "Tong nho nhat: " << getSum(arr, SIZE(arr)) << "\n";
    return 0;
}

Kết quả

Tong nho nhat: 30