सबएरे एक सरणी का सन्निकट भाग होता है। उदाहरण के लिए, हम एक सरणी [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++ में विषम योग वाले सबएरे की संख्या निकालने के लिए हर संभव जानकारी समझाएंगे। विषम योग वाले सबएरे की संख्या निकालने के लिए, हम विभिन्न दृष्टिकोणों का उपयोग कर सकते हैं, तो यहां इसका एक सरल उदाहरण है -
इनपुट: array = {9,8,7,6,5} आउटपुट: 9 व्याख्या: सबएरे का योग - {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²) है।
उदाहरण
#include <bits/stdc++.h> using namespace std; int main(){ int n=5, temp = 0; int a[n-1] = { 9,8,7,6,5 } ; // हमारी सरणी घोषित करना। int cnt = 0; // काउंटर वेरिएबल। for(int i = 0; i < n; i++){ temp = 0; // हमारे अस्थायी योग को रीफ्रेश करना। for(int j = i; j < n; j++){ // यह लूप i से 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 " स्थिति से शुरू होने वाले विषम योग वाले सबएरे को खोजने के लिए किया जाता है।
कुशल दृष्टिकोण
इस दृष्टिकोण में, हम सरणी में 0th स्थिति से प्रत्येक तत्व को प्रोसेस कर रहे हैं। यदि वर्तमान तत्व विषम है, तो एक विषम काउंटर बढ़ाएं और प्रत्येक सम संख्या के लिए एक सम काउंटर बढ़ाएं। यदि हमें एक विषम संख्या मिलती है, तो सम और विषम के मानों को स्वैप करें क्योंकि सबएरे में एक विषम संख्या जोड़ने से इसकी समता बदल जाएगी और अंत में परिणाम में काउंट जोड़ें। इस कोड की जटिलता 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}; // सरणी को इनिशियलाइज़ करना // सरणी के प्रत्येक तत्व को प्रोसेस करने के लिए फॉर लूप for ( i = 0 ; i < n ; i ++ ) { if ( arr[ i ] % 2 == 0 ) { even++; } else { // सम विषम मान स्वैप करना 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(n²) है। एक कुशल दृष्टिकोण सरणी के प्रत्येक तत्व को पार करके और प्रत्येक विषम/सम संख्या मिलने पर विषम/सम काउंटर वेरिएबल को बढ़ाकर और विषम संख्या मिलने पर काउंटर को स्वैप करके है; इस कोड की समय जटिलता O(n) है। आशा है आपको यह लेख समस्या और समाधान को समझने में उपयोगी लगा होगा।
