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

C++ में सभी सबएरे के XOR का योग

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

उदाहरण से समझते हैं

इनपुट: arr[] = {5, 1, 4} 
आउटपुट: 19
व्याख्या: 
सबएरे के XOR: 
XOR {5} = 5
XOR {1} = 1
XOR {4} = 4
XOR {5,1} = 5^1 = 4
XOR {1, 4} = 1^4 = 5
XOR {5, 1, 4} = 5^1^4 = 0
योग = 5 + 1 + 4 + 4 + 5 + 0 = 19

इस समस्या को हल करने का एक सरल तरीका नेस्टेड लूप का उपयोग करके सभी सबएरे ढूंढना है, फिर प्रत्येक सबएरे के तत्वों का XOR निकालकर योग में जोड़ना।

यह समाधान कुशल नहीं है क्योंकि इसमें लूप नेस्टेड हैं और इसकी समय जटिलता एक्सपोनेंशियल होगी।

कुशल दृष्टिकोण: प्रीफिक्स ऐरे

एक कुशल दृष्टिकोण प्रीफिक्स ऐरे का उपयोग करना है। यह प्रीफिक्स ऐरे इंडेक्स i तक सभी तत्वों के XOR को स्टोर करेगा।

prefixarr[i] = arr[0]^arr[1]^ … ^arr[i]

इसके बाद, हम इंडेक्स i से j तक के तत्वों का XOR निकालने के लिए एक सरल सूत्र लागू कर सकते हैं।

XOR(i-j) = prefixarr[j] - prefixarr[i]  (i >= 0 के लिए)
यदि i = 0, तो XOR(i-j) = prefixarr[j]

इस सूत्र का उपयोग करके हम सभी सबएरे के XOR की गणना कर सकते हैं।

C++ प्रोग्राम उदाहरण

#include <iostream>
using namespace std;

int calcSubArrayXORSum(int arr[], int n) {
    int sum = 0;
    int multiplier = 1;
    for (int i = 0; i < 30; i++) {
        int oddCount = 0;
        bool isOdd = 0;
        for (int j = 0; j < n; j++) {
            if ((arr[j] & (1 << i)) > 0)
                isOdd = (!isOdd);
            if (isOdd)
                oddCount++;
        }
        for (int j = 0; j < n; j++) {
            sum += (multiplier * oddCount);
            if ((arr[j] & (1 << i)) > 0)
                oddCount = (n - j - oddCount);
        }
        multiplier *= 2;
    }
    return sum;
}

int main() {
    int arr[] = { 3, 8, 13 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Sum of XOR of all subarrays is " << calcSubArrayXORSum(arr, n);
    return 0;
}

आउटपुट

Sum of XOR of all subarrays is 46
  1. - C++ में सभी सबसीक्वेंस के योग का योग ढूंढें

    मान लीजिए हमारे पास n एलिमेंट्स वाला एक ऐरे A है। हमें ऐरे के सभी सबसेट के योग का कुल योग ढूंढना है। तो यदि ऐरे A = [5, 6, 8] जैसा है, तो यह होगा - सबसेट योग 5 5 6 6 8 8 5,6 11 6,8 14 5,8 13 5,6,8 19 कुल योग 76 जैसा कि ऐरे में n एलिमेंट्स हैं, तो हमारे पास 2ⁿ संख्या में सबस

  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++ में एलिक्वॉट योग (Aliquot Sum)

    यहां हम देखेंगे कि एलिक्वॉट योग क्या है? n का एलिक्वॉट योग n को छोड़कर n के सभी पूर्ण गुणनखंडों का योग है। उदाहरण के लिए, यदि संख्या 20 है, तो पूर्ण गुणनखंड (1, 2, 4, 5, 10) हैं। तो एलिक्वॉट योग 22 है। एक दिलचस्प तथ्य यह है कि, यदि किसी संख्या का एलिक्वॉट योग संख्या स्वयं है, तो वह संख्या एक पूर्ण