Tìm một số có tổng nhỏ nhất khi XOR với mọi số mảng số nguyên trong C ++

Khái niệm

Đối với mảng đã cho 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 (Arr [0] XOR X) + (Arr [1] XOR X) +… + Arr [n - 1] XOR X là mức tối thiểu có thể.

Đầu vào

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

Đầu ra

X = 7, Sum = 10

Phương pháp tiếp cận

Vì vậy, chúng tôi sẽ xác minh bit ‘i’th của mọi số mảng trong biểu diễn nhị phân và xem xét và đếm những số có chứa bit‘ i’th đó được đặt thành ‘1’ vì các bit đặt này sẽ góp phần tối đa hóa tổng thay vì tối thiểu hóa. Do đó, chúng ta phải xây dựng tập hợp 'i'th bit này thành' 0 'nếu số đếm lớn hơn N / 2 và nếu số đếm nhỏ hơn N / 2 thì các số có tập bit' thứ i sẽ nhỏ hơn và do đó nó sẽ không ảnh hưởng đến câu trả lời. Chúng ta biết theo phép toán XOR trên hai bit, khi A XOR B và cả A và B giống nhau thì nó cung cấp kết quả là '0', vì vậy chúng ta sẽ xây dựng bit 'thứ i' đó trong số của chúng ta (num) thành '1', kết quả là (1 XOR 1) sẽ cho "0" và 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