सी ++ में समान और विषम तत्वों के साथ उप-सरणी गिनें

हमें सकारात्मक पूर्णांकों की एक सरणी दी गई है। लक्ष्य एक सरणी में संख्याओं के उप-सरणी को खोजना है जैसे कि प्रत्येक उप-सरणी में समान और विषम तत्वों की संख्या समान हो। यदि सरणी {1,2,3,4} है। फिर उप-सरणी {1,2}, {2,3}, {3,4}, {1,2,3,4} होंगी। ऐसे उपसरणियों की संख्या 4 है।

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

इनपुट - एआर [] ={1,3,5,7,8,3,2};

आउटपुट − समान सम और विषम तत्वों वाले उपसरणियों की संख्या है − 4

स्पष्टीकरण - उप-सरणी होगी - { 7,8 }, {8,3} {3,2}, {7,8,3,2}

इनपुट - एआर [] ={2,4,6};

आउटपुट − समान सम और विषम तत्वों वाले उपसरणियों की संख्या है − 0

स्पष्टीकरण - सभी तत्व सम हैं।

नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है

इस दृष्टिकोण में, हम सरणी तत्वों (शुरुआत में 0) के बीच अंतर के रूप में एक चर अस्थायी का उपयोग करेंगे और इसे 1 से बढ़ाएंगे यदि गिरफ्तारी [i] विषम है और इसे 1 से घटाएं यदि एआर [i] सम है। जब अस्थायी का मान खुद को दोहराता है तो इन अनुक्रमितों के बीच समान-विषम संख्याओं की समान संख्या के साथ एक उप-सरणी मौजूद होनी चाहिए। तापमान सकारात्मक भी हो सकता है और नकारात्मक भी। सकारात्मक अंतरों की आवृत्ति के लिए arr_1[size+1] और नकारात्मक अंतरों की आवृत्ति के लिए arr_2[size+1] दो हैश सरणियाँ लेना।

प्रत्येक अंतर के लिए अस्थायी <0 गिनती के लिए arr_1 [-temp] से आवृत्ति जोड़ें। [ -(-temp) ] एक सकारात्मक सूचकांक देता है।

प्रत्येक अंतर के लिए अस्थायी> 0 गिनती के लिए arr_2 [temp] से आवृत्ति जोड़ें। चूंकि समान अंतर मान की सभी घटनाएं उप-सरणी का हिस्सा होंगी। इन आवृत्तियों को 1 से अपडेट करें।

Arr[] = { 1,3,5,7,8,3,2 }

0 से शुरू होने वाले अस्थायी मान -

1,2,3,4,3,4,3
arr_1[] { 1,1,1,3,2,0,0,0 } //all differences are positive
arr_2[] { 0,0,0,0,0,0,0,0 } //no difference is negative
Adding arr_1[temp] to count in each iteration gives count=4.

उप-सरणी हैं - { 7,8 }, {8,3} {3,2}, {7,8,3,2}

• प्रारंभिक सरणी को गिरफ्तारी [] के रूप में लें।

• फ़ंक्शन Sub_even_odd(int arr[], int size) सरणी और उसकी लंबाई लेता है और समान और विषम तत्वों के साथ उप-सरणी की गिनती देता है।

• प्रारंभिक गणना को 0 के रूप में लें और चर अस्थायी को एक चर के रूप में लें जो एक विषम मान का सामना करने पर बढ़ता है और एक सम मान का सामना करने पर घटता है।

• अस्थायी की आवृत्तियों को संग्रहीत करने के लिए दो सरणियाँ arr_1[] और arr_2[] लें। arr_1[] अस्थायी के सकारात्मक मूल्यों के लिए जो आकार+1 तक हो सकता है यदि पूरी सरणी सम है।

  arr_2[] अस्थायी के नकारात्मक मानों के लिए जो आकार+1 तक हो सकता है यदि पूरी सरणी सम है।

• ट्रैवर्स एआर [] लूप के लिए उपयोग कर रहा है।

• अगर arr[i] &1==1 इसका मतलब है कि arr[i] विषम है। वृद्धि अस्थायी। और तापमान में कमी।

• अगर temp<0 तो गिनती करने के लिए arr_2[] से संबंधित आवृत्ति जोड़ें। उस आवृत्ति को 1 से बढ़ाएँ।

• अगर temp> 0 तो गिनती करने के लिए arr_1[] से संबंधित आवृत्ति जोड़ें। उस आवृत्ति को 1 से बढ़ाएँ।

• अंत में, हमने एआर [] में उप-सरणी की संख्या के रूप में गिना है जिसमें समान और विषम तत्वों की संख्या समान है

• परिणाम के रूप में वापसी की गिनती।

उदाहरण

#include <bits/stdc++.h>
using namespace std;
int Sub_even_odd(int arr[], int size){
   int count = 0;
   int temp = 0;
   int arr_1[size + 1] = {0};
   int arr_2[size + 1] = {0};
   arr_1[0] = 1;
   for (int i = 0; i < size; i++){
      if(arr[i] & 1 == 1)
         { temp++; }
      else
         { temp--; }
      if (temp < 0){
         count += arr_2[-temp];
         arr_2[-temp]++;
      }
      else{
         count += arr_1[temp];
         arr_1[temp]++;
      }
   }
   return count;
}
int main(){
   int arr[] = {3, 4, 6, 1, 2, 4, 10, 42};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of subarrays with same even and odd elements are: "<<Sub_even_odd(arr,
size);
   return 0;
}

आउटपुट

यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -

Count of subarrays with same even and odd elements are: 4