इस समस्या में, हमें n संख्याओं का एक ऐरे arr[] दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो सभी संभावित सबसेट के XOR का योग निकाले।
उदाहरण से समझते हैं
इनपुट: arr[] = {5, 1, 4}
आउटपुट: 20
व्याख्या:
सभी सबसेट के XOR:
{5} = 5
{1} = 1
{4} = 4
{5, 1} = 4
{5, 4} = 1
{1, 4} = 5
{5, 1, 4} = 0
XOR का योग = 5 + 1 + 4 + 4 + 1 + 5 = 20इस समस्या का एक सरल समाधान लूप का उपयोग करके सभी संभावित सबसेट ढूंढना और फिर प्रत्येक सबसेट के सभी तत्वों का XOR निकालकर योग को अपडेट करना है।
यह दृष्टिकोण प्रभावी नहीं है, क्योंकि बड़े मानों के लिए समय जटिलता एक्सपोनेंशियली बढ़ेगी।
कुशल दृष्टिकोण: XOR के गुणों का उपयोग
एक कुशल दृष्टिकोण XOR के गुणों का उपयोग करना है। यहां, हम ऐरे के सभी तत्वों का OR निकालेंगे और बिट्स चेक करेंगे। यदि i-वीं बिट सेट है, तो योग को (2^(n-1+i)) से अपडेट करें।
C++ प्रोग्राम उदाहरण
#include <iostream>
#include <math.h>
using namespace std;
int subSetXORSum(int arr[], int n) {
int bitOR = 0;
for (int i = 0; i < n; ++i)
bitOR |= arr[i];
return (bitOR * pow(2, n - 1));
}
int main() {
int arr[] = {1, 5, 4};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Sum of XOR of all possible subsets is " << subSetXORSum(arr, size);
return 0;
}आउटपुट
Sum of XOR of all possible subsets is 20