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

अवधारणा

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

उदाहरण

इनपुट

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

आउटपुट

X = 7, Sum = 10

दृष्टिकोण

हम सरणी की प्रत्येक संख्या के बाइनरी प्रतिनिधित्व में 'i'वें बिट की जांच करेंगे और उन संख्याओं की गिनती करेंगे जिनमें वह 'i'वां बिट '1' पर सेट है, क्योंकि ये सेट बिट्स योग को न्यूनतम करने के बजाय अधिकतम करने में योगदान करते हैं। परिणामस्वरूप, यदि गिनती N/2 से अधिक है तो हमें इस 'i'वें बिट को '0' पर बनाना होगा और यदि गिनती N/2 से कम है तो 'i'वें बिट सेट वाली संख्याएं कम हैं और परिणामस्वरूप यह उत्तर को प्रभावित नहीं करेगा। हम जानते हैं कि XOR ऑपरेशन में दो बिट्स पर, जब A XOR B और दोनों A और B समान होते हैं तो परिणाम '0' होता है, इसलिए हम अपनी संख्या (num) में उस 'i'वें बिट को '1' पर बनाएंगे, जिससे (1 XOR 1) '0' देगा और योग को न्यूनतम करेगा।

C++ कार्यान्वयन

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