सी ++ में एक सरणी में सभी जोड़े के एक्सओआर का योग

इस समस्या में, हमें n पूर्णांकों का एक सरणी arr[] दिया गया है। हमारा काम एक प्रोग्राम बनाना है जो एक सरणी में सभी जोड़े के एक्सओआर का योग खोजने के लिए है।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

Input: arr[] = {5, 1, 4}
Output: 10
Explanation: the sum of all pairs:
5 ^ 1 = 4
1 ^ 4 = 5
5 ^ 4 = 1
sum = 4 + 5 + 1 = 10

इस समस्या को हल करने का एक आसान तरीका है नेस्टेड लूप चलाना और संख्याओं के सभी जोड़े ढूंढना। प्रत्येक जोड़ी का XOR ज्ञात करें और उन्हें योग में जोड़ें।

एल्गोरिदम

Initialise sum = 0
Step 1: for(i -> 0 to n). Do:
   Step 1.1: for( j -> i to n ). Do:
      Step 1.1.1: update sum. i.e. sum += arr[i] ^ arr[j].
Step 2: return sum.

उदाहरण

हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम,

#include <iostream>
using namespace std;
int findXORSum(int arr[], int n) {
   int sum = 0;
   for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
    sum += (arr[i]^arr[j]);
   return sum;
}
int main() {
   int arr[] = { 5, 1, 4 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"Sum of XOR of all pairs in an array is "<<findXORSum(arr, n);
   return 0;
}

आउटपुट

Sum of XOR of all pairs in an array is 10

एल्गोरिथ्म की समय जटिलता O(n2) है और यह समस्या का सबसे कुशल समाधान नहीं है।

समस्या का एक कुशल समाधान बिट हेरफेर तकनीक का उपयोग करना है।

यहां, हम संख्या के बिट्स और प्रत्येक स्थिति पर विचार करेंगे। और नीचे दिए गए फॉर्मूले को लागू करें मध्यवर्ती योग ज्ञात करें,

(number of set bits) * (number of unset bits) * (2^(bit_position))

अंतिम योग खोजने के लिए, हम सभी बिट्स का मध्यवर्ती योग जोड़ देंगे।

हमारा समाधान 64-बिट पूर्णांक मान के लिए है। इस दृष्टिकोण के लिए, हमें बिट्स की संख्या चाहिए।

एल्गोरिदम

Initialize sum = 0, setBits = 0, unsetBits = 0.
Step 1: Loop for i -> 0 to 64. repeat steps 2, 3.
Step 2: Reset setBits and unsetBits to 0.
Step 3: For each element of the array find the value of setBits and unsetBits. At ith position.
Step 4: update sum += (setBits * unsetBits * (2i))

उदाहरण

हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम,

#include <iostream>
#include <math.h>
using namespace std;
long findXORSum(int arr[], int n) {
   long sum = 0;
   int unsetBits = 0, setBits = 0;
   for (int i = 0; i < 32; i++) {
      unsetBits = 0; setBits = 0;
      for (int j = 0; j < n; j++) {
         if (arr[j] % 2 == 0)
            unsetBits++;
         else
            setBits++;
         arr[j] /= 2;
      }
      sum += ( unsetBits*setBits* (pow(2,i)) );
   }
   return sum;
}
int main() {
   int arr[] = { 5, 1, 4, 7, 9};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"Sum of XOR of all pairs in an array is "<<findXORSum(arr, n);
   return 0;
}

आउटपुट

Sum of XOR of all pairs in an array is 68