यदि आपने कभी C ++ का उपयोग किया है, तो आपको पता होना चाहिए कि उप-सरणी क्या हैं और वे कितने उपयोगी हैं। जैसा कि हम जानते हैं कि C++ में हम कई गणितीय समस्याओं को आसानी से हल कर सकते हैं। तो इस लेख में, हम पूरी जानकारी की व्याख्या करेंगे कि हम C++ में इन सबएरे की मदद से M विषम संख्या कैसे प्राप्त कर सकते हैं।
इस समस्या में, हमें दिए गए सरणी और पूर्णांक m के साथ गठित कई उप-सरणी खोजने की आवश्यकता है, जहां प्रत्येक उप-सरणी में बिल्कुल m विषम संख्याएँ हों। तो यहाँ इस दृष्टिकोण का सरल उदाहरण है -
Input : array = { 6,3,5,8,9 }, m = 2
Output : 5
Explanation : Subarrays with exactly 2 odd numbers are
{ 3,5 }, { 6,3,5 }, { 3,5,8 }, { 5,8,9 }, { 6,3,5,8 }, { 3,5,8,9 }
Input : array = { 1,6,3,2,5,4 }, m = 2
Output : 6
Explanation : Subarrays with exactly 2 odd numbers are
{ 1,6,3 }, { 3,2,5 }, { 1,6,3,2 }, { 6,3,2,5 }, { 3,2,5,4 }, { 6,3,2,5,4 } पहला तरीका
इस दृष्टिकोण में, किसी दिए गए सरणी से सभी संभावित सबएरे उत्पन्न होते हैं, और प्रत्येक सबरेरे को बिल्कुल एम विषम संख्या के लिए चेक किया जाता है। यह एक सरल जनरेट और खोज दृष्टिकोण है, और इस दृष्टिकोण की समय जटिलता O(n 2 ) है )।
उदाहरण
#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 is size of array, m numbers to be find in subarrays,
// count is number of subarray with m odd numbers
for (int i = 0; i < n; i++){ // outer loop to process each element.
int odd = 0;
for (int j = i; j < n; j++) {// inner loop to find subarray with m number
if (a[j] % 2)
odd++;
if (odd == m) // if odd numbers become equals to m.
count++;
}
}
cout << "Number of subarrays with n numbers are: " << count;
return 0;
} आउटपुट
Number of subarrays with n numbers are: 6
उपरोक्त कोड की व्याख्या
इस कोड में, हम m विषम संख्याओं के साथ उप-सरणी खोजने के लिए नेस्टेड लूप का उपयोग कर रहे हैं, और बाहरी लूप का उपयोग "i" को बढ़ाने के लिए किया जाता है, जिसका उपयोग प्रत्येक तत्व को एक सरणी में संसाधित करने के लिए किया जाएगा।
इनर लूप का उपयोग सबएरे को खोजने और तत्वों को प्रोसेस करने के लिए किया जाता है जब तक कि विषम काउंटर m तक नहीं पहुंच जाता, प्रत्येक सबएरे के लिए परिणाम काउंटर काउंट को बढ़ाता है, और अंत में काउंट वेरिएबल में संग्रहीत परिणाम को प्रिंट करता है।
दूसरा तरीका
एक अन्य तरीका यह है कि "i" विषम संख्याओं के साथ उपसर्गों की संख्या को संग्रहीत करने के लिए एक सरणी बनाई जाए, प्रत्येक तत्व को संसाधित किया जाए, और प्रत्येक विषम संख्या के लिए विषम संख्याओं की संख्या बढ़ाई जाए।
जब विषम संख्याओं की संख्या m से अधिक हो जाती है या उसके बराबर हो जाती है, तो उपसर्ग सरणी में संख्या को (विषम - m ) स्थिति में जोड़ें।
जब विषम, m से अधिक या उसके बराबर हो जाता है, तो हम सूचकांक तक बनने वाले उपसरणियों की संख्या की गणना करते हैं और "विषम - 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 };
// outer loop to process every element of array
for (i = 0; i < n; i++){
prefix_array[odd] = prefix_array[odd] + 1; // implementing value at odd index in prefix_array[ ]
// if array element is odd then increment odd variable
if (array[i] % 2 == 0)
odd++;
// if Number of odd element becomes equal or greater than m
// then find the number of possible subarrays that can be formed till the index.
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 को खोजने के लिए कई विषम संख्याओं के साथ, संभावित उप-सरणी की गिनती रखने के लिए 0 से गिनें, 0 के साथ विषम, और 0 के साथ n + 1 आकार के उपसर्ग_सरणी।
लूप को समझना
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];
} इस लूप में, हम उपसर्ग_एरे [] में विषम अनुक्रमणिका पर मानों को लागू कर रहे हैं, फिर विषम संख्या मिलने पर विषम चर को बढ़ा रहे हैं। हम पाते हैं कि जब एक विषम चर m के बराबर या उससे अधिक हो जाता है, तब तक उप-सरणियों की संख्या बनाई जा सकती है।
अंत में, हम काउंट वेरिएबल में संग्रहीत m विषम संख्याओं के साथ कई सबएरे प्रिंट करते हैं और आउटपुट प्राप्त करते हैं।
निष्कर्ष
इस लेख में, हम दो दृष्टिकोणों से m विषम संख्याओं के साथ उपसरणियों की संख्या ज्ञात करने की विधि को समझते हैं -
-
प्रत्येक उपसरणी उत्पन्न करना और उसमें m विषम संख्याओं की जाँच करना, और पाए गए प्रत्येक उपश्रेणी के लिए गिनती बढ़ाना। इस कोड की समय जटिलता O(n2) है।
-
कुशल दृष्टिकोण, जो सरणी के प्रत्येक तत्व के माध्यम से जा रहा है और एक उपसर्ग सरणी बना रहा है, और एक उपसर्ग सरणी की मदद से परिणाम ढूंढ रहा है। इस कोड की समय जटिलता O(n) है।
आशा है कि आपको यह लेख समस्या और समाधान को समझने में मददगार लगा होगा।