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

C++ में सभी सबएरे के XOR के XOR पर क्वेरी


दिए गए रेंज में मौजूद सभी सबएरे के XOR की गणना करना और इसे प्रिंट करना। उदाहरण के लिए:

इनपुट: arr[] = {4, 1, 2, 3, 5}, Q = 3
क्वेरी q1 = {1, 2}
q2 = {2, 4}
q3 = {1, 4}
आउटपुट: 0 2 0
व्याख्या: जैसा कि दी गई समस्या में कहा गया है कि हमें दिए गए रेंज में मौजूद सभी सबएरे के XOR को खोजने की आवश्यकता है इसलिए क्वेरी 2 के लिए सबएरे हैं: {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}
तो जैसा कि आप देख सकते हैं तत्वों की घटनाओं की संख्या हैं:
1, 3 बार मौजूद है
2, 4 बार मौजूद है
3, 3 बार मौजूद है
अब जैसा कि हम XOR का गुण जानते हैं कि जो संख्याएं सम संख्या में मौजूद हैं वे कैंसिल हो जाती हैं इसलिए 2 कैंसिल हो गया और सिर्फ 3 और 1 का XOR रह गया और वह हमारा उत्तर था।

हमें इस समस्या में बन रहे पैटर्न को देखना होगा, और फिर इसे तदनुसार लागू करना होगा।

समाधान खोजने का दृष्टिकोण

इस समस्या में, हम समस्या में मौजूद बीच के पैटर्न को खोजने की कोशिश कर रहे हैं। जब हम उस पैटर्न को देखते हैं, तो हम इसे तदनुसार लागू करते हैं और परिणामों की जांच करते हैं।

उदाहरण

उपरोक्त दृष्टिकोण के लिए C++ कोड

#include <bits/stdc++.h>
using namespace std;

void ansQueries(int prefeven[], int prefodd[], int l, int r) {
    if ((r - l + 1) % 2 == 0) // यदि रेंज में मौजूद तत्वों की संख्या सम है
        cout << "0";
    else {
        if (l % 2 == 0) // यदि l सम है
            cout << (prefeven[r] ^ prefeven[l - 1]) << "\n";
        else // यदि l विषम है
            cout << (prefodd[r] ^ prefodd[l - 1]) << "\n";
    }
}

int main() {
    int arr[] = {4, 1, 2, 3, 5};
    int n = sizeof(arr) / sizeof(int); // हमारे एरे का आकार
    int l[] = {1, 2, 1}; // दी गई क्वेरी का बायां इंडेक्स
    int r[] = {2, 4, 4}; // दी गई क्वेरी का दायां इंडेक्स
    int q = sizeof(l) / sizeof(int); // पूछी गई क्वेरी की संख्या
    // सम और विषम इंडेक्स के लिए अलग-अलग प्रीफिक्स XOR
    int prefodd[n] = {0}, prefeven[n] = {0};
    for (int i = 1; i <= n; i++) {
        if ((i) % 2 == 0) { // यदि i सम है तो हम prefeven बदलते हैं
            prefeven[i] = arr[i - 1] ^ prefeven[i - 1];
            prefodd[i] = prefodd[i - 1];
        } else {
            prefeven[i] = prefeven[i - 1];
            prefodd[i] = prefodd[i - 1] ^ arr[i - 1];
        }
    }
    for (int i = 0; i < q; i++) {
        ansQueries(prefeven, prefodd, l[i], r[i]);
    }
    return 0;
}

आउटपुट

0 2 0

उपरोक्त कोड की व्याख्या

इस दृष्टिकोण में, हम पहले देखते हैं कि यदि हमारी रेंज का आकार सम है तो हमारा उत्तर शून्य होगा क्योंकि जब हम सभी सबएरे प्रिंट करते हैं तो हर संख्या सम बार दिखाई देती है इसलिए उनका XOR लेने पर उत्तर बस 0 होगा। अब हमारे अगले भाग के लिए जहां रेंज का आकार विषम है, इस मामले में जो संख्या विषम बार दिखाई देती है वह दी गई रेंज में सम स्थिति में होती है और हमारा उत्तर बस दी गई रेंज में सम स्थिति पर दिखाई देने वाली संख्याओं के XORs होंगे। हम दो प्रीफिक्स एरे बनाए रखते हैं जिनमें वैकल्पिक स्थितियों के XOR होते हैं क्योंकि हमारा prefeven सभी सम इंडेक्स के XOR को समाहित करता है और prefodd सभी विषम इंडेक्स के XOR को समाहित करता है। अब जब हम एक क्वेरी हल करते हैं तो हमें बस यह जांचना होगा कि हमारा l सम है या विषम और तदनुसार अपना उत्तर देना होगा।

निष्कर्ष

इस ट्यूटोरियल में, हम सभी सबएरे के XOR के XOR पर क्वेरी को हल करने की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और इसे हल करने के पूर्ण दृष्टिकोण (सामान्य) को भी सीखा। हम इसी प्रोग्राम को C, Java, Python और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह ट्यूटोरियल मददगार लगा होगा।

  1. - C++ में दिए गए XOR वाले सभी जोड़ों की गणना करें

    इस ट्यूटोरियल में, हम दिए गए XOR वाले जोड़ों की संख्या खोजने के लिए एक प्रोग्राम पर चर्चा करेंगे।इसके लिए हमें एक सरणी और एक मान प्रदान किया जाएगा। हमारा कार्य उन जोड़ों की संख्या ढूंढना है जिनका XOR दिए गए मान के बराबर है।उदाहरण#include<bits/stdc++.h> using namespace std; //returning the numb

  1. - C++ में ऐरे के सभी ट्रिपलेट्स में अधिकतम XOR मान

    इस समस्या में, हमें इंटीजर्स का एक ऐरे दिया गया है। हमारा कार्य ऐरे के सभी ट्रिपलेट्स में XOR का अधिकतम मान बनाना है।समस्या को समझने के लिए एक उदाहरण लेते हैं,इनपुट − array = {5, 6, 1, 2}आउटपुट − 6व्याख्या −सभी ट्रिपलेट्स हैं: 5^6^1 = 2 5^6^2 = 1 5^1^2 = 6 6^1^2 = 5इस समस्या को हल

  1. - C++ में योग शून्य वाले सभी उपसरणी (Subarrays) प्रिंट करें

    इस समस्या में, हमें पूर्णांक मानों की एक सरणी दी गई है और हमें इस सरणी से उन सभी उपसरणी को प्रिंट करना है जिनका योग 0 के बराबर है। विषय को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं, इनपुट: सरणी = [-5, 0, 2, 3, -3, 4, -1] आउटपुट: इंडेक्स 1 से 4 तक उपसरणी का योग 0 है। इंडेक्स 5 से 7 तक उपसरणी का यो