इस समस्या में, हमें n संख्याओं का एक सरणी aar[] दिया जाता है। हमारा काम सभी संभावित सबसेट के एक्सओआर का योग खोजने के लिए एक प्रोग्राम बनाना है।
यहां, हम सरणी के सभी सबसेट पाएंगे। फिर प्रत्येक उपसमुच्चय के लिए, हम उपसमुच्चय के तत्वों का XOR खोजेंगे और उन्हें योग चर में जोड़ देंगे।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
Input: arr[] = {5, 1, 4}
Output: 20
Explanation: XOR of all subsets:
{5} = 5
{1} = 1
{4} = 4
{5, 1} = 4
{5, 4} = 1
{1, 4} = 5
{5, 1, 4} = 0
Sum of XOR = 5 + 1 + 4 + 4 + 1 + 5 = 20 समस्या का एक सरल समाधान है, लूप का उपयोग करना और सरणी के सभी संभावित उपसमुच्चय को ढूंढना और फिर प्रत्येक उपसमुच्चय के लिए सभी तत्वों का XOR खोजना और योग को अद्यतन करना। अंत में योग लौटाएं।
यह एक प्रभावी तरीका नहीं है, बड़े मूल्य के लिए, समय जटिलता तेजी से बढ़ेगी।
एक कुशल दृष्टिकोण XOR के गुणों का उपयोग कर रहा है। यहां, हम सरणी के सभी तत्वों में से OR पाएंगे और बिट्स की जांच करेंगे। यदि ith सेट है, तो योग को (2^(n-1+i)) से अपडेट करें।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम,
#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);
} आउटपुट
Sum of XOR of all possible subsets is 20