C++에서 정수 배열의 모든 수와 XOR할 때 최소 합계를 제공하는 숫자 찾기

컨셉

음이 아닌 정수의 주어진 배열 Arr[]과 관련하여 작업은 (Arr[0] XOR X) + (Arr[1] XOR X) + … + Arr[n – 1]과 같은 정수 X를 결정하는 것입니다. XOR X는 가능한 최소값입니다.

입력

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

출력

X = 7, Sum = 10

접근

그래서 우리는 이진 표현에서 배열의 모든 수의 'i' 비트를 확인하고 '1'로 설정된 'i' 비트를 포함하는 숫자를 고려하고 계산할 것입니다. 이러한 세트 비트는 최소화 대신 합계를 최대화하는 데 기여할 것이기 때문입니다. 결과적으로 카운트가 N/2보다 크면 'i' 비트를 '0'으로 설정하고 카운트가 N/2보다 작으면 'i' 비트 세트를 갖는 숫자가 더 작아야 합니다. 그 결과 답변에 영향을 미치지 않습니다. 두 비트에 대한 XOR 연산에 따라 A XOR B와 A와 B가 모두 같을 때 결과를 '0'으로 제공하므로 숫자(num)의 'i' 비트를 '1'로 빌드합니다. 결과적으로 (1 XOR 1)은 '0'을 제공하고 합계를 최소화합니다.

예

// 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;
}

출력

X = 7, Sum = 10