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

C++ में m विषम संख्या वाले सबएरे की संख्या


यदि आपने कभी C++ का उपयोग किया है, तो आपको पता होगा कि सबएरे क्या हैं और वे कितने उपयोगी हैं। जैसा कि हम जानते हैं कि, C++ में, हम कई गणितीय समस्याओं को आसानी से हल कर सकते हैं। तो इस लेख में, हम पूरी जानकारी समझाएंगे कि कैसे हम C++ में इन सबएरे की मदद से M विषम संख्या ढूंढ सकते हैं।

इस समस्या में, हमें दी गई सरणी और पूर्णांक m से बने कई सबएरे ढूंढने की आवश्यकता है जहां प्रत्येक सबएरे में ठीक m विषम संख्याएं हों। तो यहां इस दृष्टिकोण का एक सरल उदाहरण है -

इनपुट: array = { 6,3,5,8,9 }, m = 2 आउटपुट: 5 व्याख्या: ठीक 2 विषम संख्या वाले सबएरे हैं { 3,5 }, { 6,3,5 }, { 3,5,8 }, { 5,8,9 }, { 6,3,5,8 }, { 3,5,8,9 } इनपुट: array = { 1,6,3,2,5,4 }, m = 2 आउटपुट: 6 व्याख्या: ठीक 2 विषम संख्या वाले सबएरे हैं { 1,6,3 }, { 3,2,5 }, { 1,6,3,2 }, { 6,3,2,5 }, { 3,2,5,4 }, { 6,3,2,5,4 }

पहला दृष्टिकोण

इस दृष्टिकोण में, दी गई सरणी से सभी संभावित सबएरे जनरेट किए जाते हैं, और प्रत्येक सबएरे को ठीक m विषम संख्या के लिए चेक किया जाता है। यह एक सरल जनरेट और फाइंड दृष्टिकोण है, और इस दृष्टिकोण की समय जटिलता O(n²) है।

उदाहरण

 #include <bits/stdc++.h> using namespace std; int main (){     int a[] = { 1, 6, 3, 2, 5, 4 };     int n = 6, m = 2, count = 0; // n सरणी का आकार है, m सबएरे में ढूंढी जाने वाली संख्या,                               // count m विषम संख्या वाले सबएरे की संख्या है     for (int i = 0; i < n; i++){ // प्रत्येक तत्व को प्रोसेस करने के लिए बाहरी लूप।         int odd = 0;         for (int j = i; j < n; j++) {// m संख्या वाले सबएरे को खोजने के लिए आंतरिक लूप             if (a[j] % 2)                 odd++;             if (odd == m) // यदि विषम संख्या m के बराबर हो जाती है।                 count++;         }     }     cout << "Number of subarrays with n numbers are: " << count;     return 0; }

आउटपुट

Number of subarrays with n numbers are: 6

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

इस कोड में, हम m विषम संख्या वाले सबएरे को खोजने के लिए नेस्टेड लूप का उपयोग कर रहे हैं, और बाहरी लूप का उपयोग "i" को बढ़ाने के लिए किया जाता है, जिसका उपयोग सरणी में प्रत्येक तत्व को प्रोसेस करने के लिए किया जाएगा।

आंतरिक लूप का उपयोग सबएरे खोजने और तत्वों को प्रोसेस करने के लिए किया जाता है जब तक विषम काउंटर m तक नहीं पहुंच जाता, प्रत्येक सबएरे के लिए परिणाम काउंटर count बढ़ाते हैं, और अंत में count वेरिएबल में स्टोर परिणाम प्रिंट करते हैं।

दूसरा दृष्टिकोण

एक अन्य दृष्टिकोण "i" विषम संख्या वाले प्रीफिक्स की संख्या स्टोर करने के लिए एक सरणी बनाना है, प्रत्येक तत्व को प्रोसेस करना, और प्रत्येक विषम संख्या मिलने पर विषम संख्याओं की संख्या बढ़ाना।

जब विषम संख्याओं की गिनती m से अधिक या बराबर हो जाती है, तो प्रीफिक्स सरणी में (odd - m) स्थिति पर संख्या जोड़ें।

जब विषम m से अधिक या बराबर हो जाता है, तो हम इंडेक्स तक बने सबएरे की संख्या की गणना करते हैं और "odd - m" संख्याओं को काउंट वेरिएबल में जोड़ते हैं। परिणाम हर तत्व के प्रोसेस होने के बाद काउंट वेरिएबल में स्टोर होता है।

उदाहरण

 #include <bits/stdc++.h> using namespace std; int main (){     int array[ ] = { 1, 6, 3, 2, 5, 4 };     int n = 6, m = 2, count = 0, odd = 0, i;     int prefix_array[n + 1] = { 0 };     // सरणी के प्रत्येक तत्व को प्रोसेस करने के लिए बाहरी लूप     for (i = 0; i < n; i++){         prefix_array[odd] = prefix_array[odd] + 1;    // प्रीफिक्स_सरणी[ ] में odd इंडेक्स पर मान लागू करना         // यदि सरणी तत्व विषम है तो odd वेरिएबल बढ़ाना         if (array[i] % 2 == 0)             odd++;         // यदि विषम तत्वों की संख्या m के बराबर या अधिक हो जाती है         //  तब इंडेक्स तक बनने वाले संभावित सबएरे की संख्या खोजें।         if (odd >= m)             count += prefix_array[odd - m];     }     cout << "Number of subarrays with n numbers are: " << count;     return 0; }

आउटपुट

Number of subarrays with n numbers are: 6

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

सरणी और वेरिएबल को शुरुआती मानों के साथ इनिशियलाइज़ करना -

int array[ 6 ] = { 1, 6, 3, 2, 5, 4 }; int n = 6, m = 2, count = 0, odd = 0, i; int prefix_array[n + 1] = { 0 };

इसमें, हम वेरिएबल n को सरणी के आकार के साथ इनिशियलाइज़ कर रहे हैं, m को सबएरे में खोजी जाने वाली विषम संख्या की संख्या के साथ, count को 0 के साथ संभावित सबएरे की गिनती रखने के लिए, odd को 0 के साथ, और prefix_array को आकार n + 1 के साथ 0 से।

लूप को समझना

for (i = 0; i < n; i++){    prefix_array[odd] = prefix_array[odd] + 1;    if (array[i] % 2 == 0)       odd++;       if (odd >= m)          count += prefix_array[odd - m]; }

इस लूप में, हम prefix_array[ ] में odd इंडेक्स पर मान लागू कर रहे हैं, फिर विषम संख्या मिलने पर odd वेरिएबल बढ़ा रहे हैं। जब odd वेरिएबल m के बराबर या अधिक हो जाता है तो इंडेक्स तक बनने वाले सबएरे की संख्या खोजते हैं।

अंत में, हम count वेरिएबल में स्टोर m विषम संख्या वाले सबएरे की संख्या प्रिंट करते हैं और आउटपुट प्राप्त करते हैं।

निष्कर्ष

इस लेख में, हम दो दृष्टिकोणों से m विषम संख्या वाले सबएरे की संख्या निकालने का दृष्टिकोण समझते हैं -

  • हर सबएरे को जनरेट करना और उसमें m विषम संख्या चेक करना, और प्रत्येक सबएरे के लिए काउंट बढ़ाना। इस कोड की समय जटिलता O(n²) है।

  • कुशल दृष्टिकोण, जो सरणी के प्रत्येक तत्व को पार करके और एक प्रीफिक्स सरणी बनाकर, और प्रीफिक्स सरणी की मदद से परिणाम निकालता है। इस कोड की समय जटिलता O(n) है।

आशा है आपको यह लेख समस्या और समाधान को समझने में उपयोगी लगा होगा।

  1. C++ का उपयोग करके पेंटागोनल पिरामिडल संख्या ज्ञात करना C++ का उपयोग करके पेंटागोनल पिरामिडल संख्या ज्ञात करना

    एक पेंटागोनल पिरामिडल संख्या पेंटागोनल बेस पिरामिड में वस्तुओं की संख्या के बराबर होती है। नीचे कुछ पेंटागोनल संख्याएं देखें। N तक पेंटागोनल संख्याओं का योग Nवीं पेंटागोनल पिरामिडल संख्या के बराबर होता है। इस लेख में, हम Nवीं पेंटागोनल पिरामिडल संख्या खोजने पर चर्चा करेंगे, उदाहरण के लिए: इनपुट:

  1. C++ में स्ट्रिंग के सबस्ट्रिंग्स की संख्या निकालना C++ में स्ट्रिंग के सबस्ट्रिंग्स की संख्या निकालना

    इस लेख में, आप एक दी गई स्ट्रिंग में बनने वाले सबस्ट्रिंग्स (गैर-खाली) की संख्या निकालने के दृष्टिकोण के बारे में जानेंगे।इनपुट: string = moon आउटपुट: 10 व्याख्या: सबस्ट्रिंग्स हैं m, o, o, n, mo, oo, on, moo, oon और moon। इनपुट: string = yellow आउटपुट: 21समाधान खोजने का दृष्टिकोणमान लें स्ट्रिंग की

  1. C++ का उपयोग करके स्टॉपिंग स्टेशनों की संख्या ज्ञात करें C++ का उपयोग करके स्टॉपिंग स्टेशनों की संख्या ज्ञात करें

    बिंदु X और Y के बीच n संख्या में इंटरमीडिएट ट्रेन स्टेशन हैं। उन विभिन्न तरीकों की गणना करें जिनसे ट्रेनों को s स्टेशनों पर रुकने के लिए व्यवस्थित किया जा सकता है जैसे कि कोई दो स्टेशन एक-दूसरे के बगल में न हों। तो इस लेख में, हम स्टॉपिंग स्टेशनों की संख्या ज्ञात करने के लिए हर संभव दृष्टिकोण की व्य