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

C++ में आकार k की उप-सरणी का अधिकतम XOR मान ज्ञात करें


इस समस्या में, हमें n तत्वों वाली एक सरणी arr[] और एक पूर्णांक k दिया गया है। हमारा कार्य आकार k की उप-सरणी का अधिकतम XOR मान ज्ञात करना है।

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

इनपुट

arr[] = {3, 1, 6, 2 ,7, 9} k = 3

आउटपुट

12

व्याख्या

आकार k की सभी उप-सरणी और सभी तत्वों का XOR:

{3, 1, 6} = 4 {1, 6, 2} = 5 {6, 2, 7} = 3 {2, 7, 9} = 12

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

समस्या का एक सरल समाधान दो लूप का उपयोग करना है। एक सरणी पर पुनरावृति करने के लिए और दूसरा उप-सरणी के सभी तत्वों का XOR खोजने के लिए। और फिर सभी में से अधिकतम लौटाएँ।

यह समाधान ठीक है लेकिन एक बेहतर दृष्टिकोण बनाया जा सकता है। हमें इंडेक्स 0 से शुरू होने वाली आकार k की उप-सरणी द्वारा योग खोजने की आवश्यकता है। और फिर सरणी पर पुनरावृति करके एक नए तत्व को XOR में जोड़ना और पहले को हटाना। विलोपन सूत्र x^a^x = a का उपयोग करके संभव है।

इसलिए, प्रत्येक पुनरावृत्ति के लिए हम पहले XOR ^ arr[i - k] करेंगे, जो अंतिम इंडेक्स + 1 से वर्तमान इंडेक्स - 1 तक की उप-सरणी का मान देगा।

फिर हम उप-सरणी के XOR को arr[i] के साथ करेंगे, वर्तमान XOR प्राप्त करने के लिए। हम सभी XOR में से अधिकतम मान खोजेंगे और लौटाएँगे।

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

उदाहरण

#include<iostream> using namespace std; int findMaxSubArrayXOR(int arr[] , int n , int k) {    int currentXORVal = 0 ;    for (int i = 0 ; i < k ; i++)    currentXORVal = currentXORVal ^ arr[i];    int maxXor = currentXORVal;    for (int i = k ; i < n; i++) {       currentXORVal = currentXORVal ^ arr[i-k];       currentXORVal = currentXORVal ^ arr[i];       maxXor = max(maxXor, currentXORVal);    }    return maxXor; } int main() {    int arr[] = {3, 1, 6, 2, 7, 9};    int n = sizeof(arr)/sizeof(arr[0]);    int k = 3;    cout<<"The maximum XOR of subarray of size "<<k<<" is "<<findMaxSubArrayXOR(arr, n, k);    return 0; }

आउटपुट

The maximum XOR of subarray of size 3 is 12

  1. - C++ में अधिकतम आकार 2 और दी गई वैल्यू द्वारा सीमित योग के साथ न्यूनतम पार्टीशन

    समस्या विवरण सकारात्मक संख्याओं का एक ऐरे arr[] दिया गया है, ऐरे में न्यूनतम संख्या में सेट ढूंढें जो निम्नलिखित गुण को संतुष्ट करते हैं: एक सेट में अधिकतम दो एलिमेंट्स हो सकते हैं। दोनों एलिमेंट्स का सन्निकट होना आवश्यक नहीं है। सेट के एलिमेंट्स का योग दी गई Key से कम या बराबर होना चाहिए। यह माना

  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++ प्रोग्राम: सरणी में सबसे छोटे मान की आवृत्ति ज्ञात करना

    यहां हम देखेंगे कि सरणी में सबसे छोटे तत्व की आवृत्ति कैसे ज्ञात करें। मान लें सरणी तत्व [5, 3, 6, 9, 3, 7, 5, 8, 3, 12, 3, 10] हैं, यहां सबसे छोटा तत्व 3 है, और इस तत्व की आवृत्ति 4 है। इसलिए आउटपुट 4 है। इसे हल करने के लिए हम सूची का सबसे छोटा तत्व ज्ञात करेंगे, फिर पहले नंबर की घटनाओं को गिनेंगे