Subarrays एक array का सन्निहित हिस्सा हैं। उदाहरण के लिए, हम एक सरणी [5, 6, 7, 8] पर विचार करते हैं, फिर दस गैर-रिक्त उपसरणियाँ हैं जैसे (5), (6), (7), (8), (5, 6), (6) ,7), (7,8), (5,6,7), (6,7,8) और (5,6,7,8)।
इस गाइड में, हम C++ में विषम योगों के साथ उपसरणियों की संख्या ज्ञात करने के लिए हर संभव जानकारी की व्याख्या करेंगे। विषम योग के साथ उपसरणियों की संख्या ज्ञात करने के लिए, हम विभिन्न दृष्टिकोणों का उपयोग कर सकते हैं, इसलिए यहां इसके लिए एक सरल उदाहरण दिया गया है -
Input : array = {9,8,7,6,5}
Output : 9
Explanation :
Sum of subarray -
{9} = 9
{7} = 7
{5} = 5
{9,8} = 17
{8,7} = 15
{7,6} = 13
{6,5} = 11
{8,7,6} = 21
{9,8,7,6,5} = 35 क्रूर फ़ोर्स अप्रोच
इस दृष्टिकोण के साथ हम केवल यह जांच सकते हैं कि सभी उप-सरणियों में तत्वों का योग सम है या विषम, यदि यह भी है तो हम उस उप-सरणी को अस्वीकार कर देंगे और विषम राशि के साथ उप-सरणी की गणना करेंगे, यह एक कुशल दृष्टिकोण नहीं है क्योंकि इस कोड की जटिलता O है (n 2 )।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int main(){
int n=5, temp = 0;
int a[n-1] = { 9,8,7,6,5 } ; // declaring our array.
int cnt = 0; // counter variable.
for(int i = 0; i < n; i++){
temp = 0; // refreshing our temp sum.
for(int j = i; j < n; j++){ // this loop will make our subarrays starting from i till n-1.
temp = temp + a[j];
if( temp % 2 == 1 )
cnt++;
}
}
cout << "Number of subarrays with odd sum : " << cnt << "\n";
return 0;
} आउटपुट
Number of subarrays with odd sum : 9
उपरोक्त कोड की व्याख्या
इस कोड में नेस्टेड लूप का उपयोग किया जाता है जहां बाहरी लूप का उपयोग I के मान को बढ़ाने के लिए किया जाता है, जो कि सरणी के प्रत्येक मान को प्रारंभ से इंगित कर रहा है; इनर लूप का उपयोग " i " . स्थिति से शुरू होने वाले सबअरे को खोजने के लिए किया जाता है विषम राशि होना।
कुशल दृष्टिकोण
इस दृष्टिकोण में, हम प्रत्येक तत्व को सरणी में 0 वें स्थान से संसाधित कर रहे हैं। यदि वर्तमान तत्व विषम है, तो विषम काउंटर बढ़ाएँ और प्रत्येक सम संख्या के लिए सम काउंटर बढ़ाएँ। यदि हमें एक विषम संख्या मिलती है, तो सम और विषम के मानों की अदला-बदली करें क्योंकि उप-सरणी में एक विषम संख्या जोड़ने से इसकी समता बदल जाएगी और अंत में परिणाम में एक संख्या जुड़ जाएगी। इस कोड की जटिलता O(n) है, क्योंकि हम प्रत्येक तत्व को संसाधित कर रहे हैं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int main(){
int odd = 0, even = 0, result = 0,n=5,i,temp;
int arr[ n-1 ] = { 9,8,7,6,5}; // initialising the array
// for loop for processing every element of array
for ( i = 0 ; i < n ; i ++ ) {
if ( arr[ i ] % 2 == 0 ) {
even++;
} else {
// swapping even odd values
temp = even;
even = odd;
odd = temp + 1;
}
result += odd;
}
cout << "Number of subarrays with odd sum : " << result;
} आउटपुट
Number of subarrays with odd sum : 9
उपरोक्त कोड की व्याख्या
इस कोड में, हम सम/विषम के लिए प्रत्येक अवयव की जांच करते हैं और सम संख्या के लिए इंक्रीमेंट इवन काउंटर और विषम संख्या के लिए विषम काउंटर की जांच करते हैं। साथ ही, यदि कोई विषम संख्या पाई जाती है, तो हम विषम-सम काउंटर मानों की अदला-बदली कर रहे हैं; अन्यथा, यह सबएरे की समता को बदल देगा। फिर प्रत्येक पुनरावृत्ति के बाद परिणाम चर में विषम काउंटर का मान जोड़ना।
निष्कर्ष
इस लेख में, हमने समझाया कि ब्रूट फोर्स दृष्टिकोण से सम विषम के साथ उपसरणियों की संख्या का पता कैसे लगाया जाए, जो हर उपसरणी को विषम राशि के साथ उत्पन्न कर रहा है और गिनती में वृद्धि कर रहा है। इस कोड की समय जटिलता O(n2) है। एक कुशल दृष्टिकोण सरणी के प्रत्येक तत्व के माध्यम से जा रहा है और प्रत्येक विषम/सम संख्या के साथ विषम/सम काउंटर चर में वृद्धि और एक विषम संख्या पाए जाने पर काउंटरों को स्वैप करना; इस कोड की समय जटिलता ओ (एन) है। आशा है कि आपको यह लेख समस्या और समाधान को समझने में मददगार लगा होगा।