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

C++ में पूर्णांकों की स्ट्रीम में दिए गए पूर्णांक का अधिकतम XOR ज्ञात करें


इस समस्या में, हमें Q क्वेरी दी गई हैं जिनमें से प्रत्येक निम्न प्रकार की है:

प्रकार 1 - सम्मिलन (1, i) मान i वाले तत्व को अपने डेटा संरचना में जोड़ने के लिए।

प्रकार 2 - findXOR (2, i), डेटा संरचना के सभी तत्वों का तत्व i के साथ XOR खोजने के लिए।

डेटा संरचना में प्रारंभ में केवल 1 तत्व होगा जो 0 होगा।

आइए एक उदाहरण से समझते हैं:

इनपुट

Queries: (1, 9), (1, 3), (1, 7), (2, 8), (1, 5), (2, 12)

आउटपुट

15 15

व्याख्या

प्रत्येक क्वेरी को हल करते हुए, (1, 9) => डेटा संरचना => {9} (1, 3) => डेटा संरचना => {9, 3} (1, 7) => डेटा संरचना => {9, 3, 7} (2, 8) => अधिकतम XOR(_, 8) = 15, XOR(7, 8) (1, 5) => डेटा संरचना => {9, 3, 7, 5} (2, 12) => अधिकतम XOR(_, 12) = 15, XOR(3, 12)

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

समस्या का समाधान ट्राई डेटा संरचना का उपयोग करके पाया जा सकता है, जो एक विशेष प्रकार का खोज ट्री है। हम एक ट्राई का उपयोग करेंगे जिसमें प्रत्येक नोड के दो चाइल्ड नोड होते हैं जो एक संख्या के बाइनरी मानों को संग्रहीत करते हैं। इसके बाद हम टाइप 1 की प्रत्येक क्वेरी के लिए संख्या के बाइनरी मान को ट्राई में जोड़ेंगे। टाइप 2 की क्वेरी के लिए, हम दिए गए मान के लिए ट्राई में पथ खोजेंगे और फिर लेवल काउंट परिणाम देगा।

ट्राई पर अधिक जानकारी के लिए, ट्राई डेटा संरचना देखें।

हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम:

उदाहरण

#include<bits/stdc++.h> using namespace std; struct Trie {    Trie* children[2];    bool isLeaf; }; bool check(int N, int i) {    return (bool)(N & (1<<i)); } Trie* newNode() {    Trie* temp = new Trie;    temp->isLeaf = false;    temp->children[0] = NULL;    temp->children[1] = NULL;    return temp; } void insertVal(Trie* root, int x) {    Trie* val = root;    for (int i = 31; i >= 0; i--) {       int f = check(x, i);       if (! val->children[f])          val->children[f] = newNode();          val = val->children[f];    }    val->isLeaf = true; } int solveQueryType2(Trie *root, int x){    Trie* val = root;    int ans = 0;    for (int i = 31; i >= 0; i--) {       int f = check(x, i);       if ((val->children[f ^ 1])){          ans = ans + (1 << i);          val = val->children[f ^ 1];       }       else       val = val->children[f];    }    return ans; } void solveQueryType1(Trie *root, int x){    insertVal(root, x); } int main(){    int Q = 6;    int query[Q][2] = {{1, 9}, {1, 3}, {1, 7}, {2, 8}, {1, 5}, {2, 12}};    Trie* root = newNode();    for(int i = 0; i < Q; i++){       if(query[i][0] == 1 ){          solveQueryType1(root, query[i][1]);          cout<<"Value inserted to the data Structure. value =          "<<query[i][1]<<endl;       }       if(query[i][0] == 2){          cout<<"The maximum XOR with "<<query[i][1]<<" is          "<<solveQueryType2(root, query[i][1])<<endl;       }    }    return 0; }

आउटपुट

Value inserted to the data Structure. value = 9 Value inserted to the data Structure. value = 3 Value inserted to the data Structure. value = 7 The maximum XOR with 8 is 15 Value inserted to the data Structure. value = 5 The maximum XOR with 12 is 15

  1. - C++ में दी गई संख्या के अंकों का उपयोग करके बनने वाली अधिकतम संख्या ज्ञात करें

    मान लीजिए हमारे पास n अंकों की एक संख्या है। हमें उस संख्या के सभी अंकों का उपयोग करके प्राप्त की जा सकने वाली अधिकतम संख्या ढूंढनी है। इसलिए यदि संख्या 339625 है, तो अधिकतम संख्या 965332 हो सकती है। समस्या से, हम देख सकते हैं कि हम आसानी से अंकों को गैर-बढ़ते क्रम में सॉर्ट कर सकते हैं, फिर उन्हें

  1. - C++ प्रोग्राम: क्रमबद्ध सरणी में दिए गए मान के k निकटतम तत्व ज्ञात करना

    मान लें हमारे पास कुछ तत्वों के साथ एक सरणी A है। हमारे पास दो अन्य मान X और k हैं। हमारा कार्य सरणी A से X के k निकटतम तत्वों की संख्या ज्ञात करना है। यदि तत्व X सरणी में मौजूद है, तो यह आउटपुट में नहीं दिखाया जाएगा। यदि A = [12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56] और X = 35, k = 4 है।

  1. - C++ में दिए गए उत्पाद के साथ N पूर्णांकों का अधिकतम GCD

    मान लीजिए हमारे पास दो पूर्णांक N और P हैं। P, N अज्ञात पूर्णांकों का उत्पाद है। हमें उन पूर्णांकों के अधिकतम संभव GCD को ढूंढना है। मान लीजिए N = 3, और P = 24, तो अलग-अलग समूह होंगे जैसे {1, 1, 24}, {1, 2, 12}, {1, 3, 8}, {1, 4, 6}, {2, 2, 6}, {2, 3, 4}। GCD हैं: 1, 1, 1, 1, 2, 1। तो उत्तर यहां 2 ह