Tìm số nguyên X cho tổng XOR với mọi phần tử mảng là nhỏ nhất trong C++

Khái niệm

Cho mảng Arr[] gồm các số nguyên không âm, nhiệm vụ là xác định một số nguyên X sao cho tổng (Arr[0] XOR X) + (Arr[1] XOR X) + … + (Arr[n-1] XOR X) đạt giá trị nhỏ nhất có thể.

Đầu vào

Arr[] = {3, 4, 5, 6, 7}

Đầu ra

X = 7, Sum = 10

Phương pháp

Ta kiểm tra bit thứ i của mọi số trong mảng dưới dạng nhị phân và đếm số lượng phần tử có bit thứ i bằng 1. Các bit 1 này sẽ làm tăng tổng thay vì giảm tổng. Do đó, ta thiết lập bit thứ i của X bằng 0 nếu số lượng bit 1 lớn hơn N/2; ngược lại, nếu số lượng bit 1 nhỏ hơn N/2 thì các bit này không ảnh hưởng lớn đến kết quả. Theo tính chất XOR: A XOR B = 0 khi A = B, nên ta đặt bit thứ i của X = 1 để (1 XOR 1) = 0, giúp giảm thiểu tổng.

Ví dụ

// C++ implementation of the approach
#include <bits/stdc++.h>
#include <cmath>
using namespace std;

void findX1(int arr1[], int n1){
    int* itr1 = max_element(arr1, arr1 + n1);
    int p1 = log2(*itr1) + 1;
    int X1 = 0;
    for (int i = 0; i < p1; i++) {
        int count1 = 0;
        for (int j = 0; j < n1; j++) {
            if (arr1[j] & (1 << i)) {
                count1++;
            }
        }
        if (count1 > (n1 / 2)) {
            X1 += 1 << i;
        }
    }
    long long int sum1 = 0;
    for (int i = 0; i < n1; i++)
        sum1 += (X1 ^ arr1[i]);
    cout << "X = " << X1 << ", Sum = " << sum1;
}

// Driver code
int main(){
    int arr1[] = { 3, 4, 5, 6, 7 };
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    findX1(arr1, n1);
    return 0;
}

Đầu ra

X = 7, Sum = 10