C++の整数配列のすべての数とXORするときに最小の合計を与える数を見つけます

コンセプト

非負の整数の与えられた配列Arr[]に関して、タスクは（Arr [0] XOR X）+（Arr [1] XOR X）+…+ Arr [n –1]となる整数Xを決定することです。 XORXは可能な限り最小限です。

入力

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

出力

X = 7, Sum = 10

アプローチ

したがって、バイナリ表現で配列のすべての数の「i」番目のビットを検証し、「1」に設定された「i」番目のビットを含む数を検討してカウントします。これらの設定されたビットは、最小化ではなく合計の最大化に寄与するためです。この結果、カウントがN / 2より大きい場合、このセットの「i」番目のビットを「0」に構築する必要があります。カウントがN / 2より小さい場合、「i」番目のビットが設定されている数値は少なくなります。この結果、答えに影響を与えることはありません。 2ビットの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