Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में सभी संभावित सबसेट के XOR का योग

इस समस्या में, हमें 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
  1. C++ में सभी संभावित फुल बाइनरी ट्रीज़ C++ में सभी संभावित फुल बाइनरी ट्रीज़

    मान लीजिए एक फुल बाइनरी ट्री एक बाइनरी ट्री है जहां प्रत्येक नोड के ठीक 0 या 2 बच्चे होते हैं। इसलिए हमें N नोड्स वाले सभी संभावित फुल बाइनरी ट्रीज़ की सूची ढूंढनी है। उत्तर में प्रत्येक ट्री के प्रत्येक नोड का node.val = 0 होना चाहिए। लौटाए गए ट्री किसी भी क्रम में हो सकते हैं। यदि इनपुट 7 है, तो ट

  1. - C++ में XOR ऑपरेशन द्वारा सरणी योग न्यूनतम करें

    समस्या विवरण एक सरणी दी गई है, एक मान X ढूंढें जिससे प्रत्येक तत्व के साथ XOR करने के बाद सरणी का योग न्यूनतम हो। उदाहरण: arr = {8, 5, 7, 6, 9} यदि X = 5, तो XOR के बाद: 13, 0, 2, 3, 12 → योग = 30 (न्यूनतम) एल्गोरिदम 32-बिट बिटमैप बनाएं प्रत्येक तत्व के सेट बिट्स गिनें n/2 हैं, तो X में वह बिट

  1. - C++ प्रोग्राम: दिए गए तत्वों के सभी संभावित कॉम्बिनेशन उत्पन्न करना

    यह C++ प्रोग्राम दिए गए कैरेक्टर ऐरे (जैसे a, b, c, d, e) के सभी संभावित कॉम्बिनेशन (संयोजन) उत्पन्न करता है। यह रिकर्सिव बैकट्रैकिंग दृष्टिकोण का उपयोग करता है। एल्गोरिदम reqLen तो लौटें - अन्यथा यदि currLen == reqLen तो नई जनरेटेड सीक्वेंस प्रिंट करें - यदि start == len तो लौटें (कोई