C++ में पूर्णांक की प्रत्येक संख्या के साथ XOR होने पर न्यूनतम योग देने वाली संख्या ज्ञात कीजिए

अवधारणा

गैर-ऋणात्मक पूर्णांकों के दिए गए सरणी Arr[] के संबंध में, कार्य एक पूर्णांक X को इस प्रकार निर्धारित करना है कि (Arr[0] XOR X) + (Arr[1] XOR X) +… + Arr[n - 1] एक्सओआर एक्स न्यूनतम संभव है।

इनपुट

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

आउटपुट

X = 7, Sum = 10

दृष्टिकोण

इसलिए हम द्विआधारी प्रतिनिधित्व में सरणी की प्रत्येक संख्या के 'i'th बिट को सत्यापित करेंगे और उन संख्याओं पर विचार करेंगे और गिनेंगे जिनमें 'i'th बिट '1' पर सेट है क्योंकि ये सेट बिट्स न्यूनतम के बजाय योग को अधिकतम करने में योगदान देंगे। इसके परिणामस्वरूप, हमें यह सेट 'i'th bit to '0' बनाना होगा यदि गिनती N/2 से अधिक है और यदि गिनती N/2 से कम है तो 'i'th bit set वाली संख्याएँ कम हैं और इसके परिणामस्वरूप यह उत्तर को प्रभावित नहीं करेगा। हम दो बिट्स पर एक्सओआर ऑपरेशन के अनुसार जानते हैं, जब ए एक्सओआर बी और ए और बी दोनों समान होते हैं तो यह '0' के रूप में परिणाम प्रदान करता है, इसलिए हम उस 'i'th बिट को हमारी संख्या (संख्या) से '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