हमें एक सरणी गिरफ्तारी [] दी गई है जिसमें केवल 0 और 1 है। लक्ष्य गिरफ्तारी के सभी उप-सरणी [] को गिनना है जैसे कि प्रत्येक उपसरणी में केवल 0 या केवल 1 दोनों नहीं हैं। यदि सरणी [1,0,0] है। सबअरे केवल 0 के [0], [0], [0,0] और केवल 1 के [1] के लिए होंगे।
आइए उदाहरणों से समझते हैं।
इनपुट - एआर [] ={ 0, 0, 1, 1, 1, 0};
आउटपुट − केवल 0 वाली उप-सरणी हैं :4 केवल 1 वाली उप-सरणी हैं:6
स्पष्टीकरण - सुबारे होंगे -
For all 0’s: [0], [0], [0], [0,0]. Total 4 ( arr[0], arr[1], arr[5], arr[0-1] ) For all 1’s: [1], [1], [1], [1,1], [1,1], [1,1,1]. Total 6 ( arr[2], arr[2], arr[4], arr[2-3], arr[3-4], arr[2-4] )
इनपुट - गिरफ्तार [] ={ 1,0,1,0 };
आउटपुट − केवल 0 वाली उप-सरणी हैं:2 केवल 1 वाली उप-सरणी हैं:2
स्पष्टीकरण - सुबारे होंगे -
For all 0’s: [0], [0]. Total 2 ( arr[1], arr[3] ) For all 1’s: [1], [1]. Total 2 ( arr[0], arr[2] )
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
हम केवल 0 और 1 के साथ अलग-अलग उप-सरणी गिनने के लिए सरणी को दो बार पार करेंगे। सरणी में लगातार 0 और 1 की गिनती संग्रहीत करने के लिए दो काउंटर काउंट_0 और काउंट_1 लें। ऐसी प्रत्येक गणना के लिए, संभावित उप-सरणी होगी count_0*(count_0+1)/2 और इसी तरह count_1 के लिए।
सरणी के अंत तक पहुंचने तक इसे कुल_0 गिनती में जोड़ें। 1 के लिए इसी तरह की प्रक्रिया करें।
-
संख्याओं की एक सरणी गिरफ्तारी [] लें।
-
फ़ंक्शन sub_zero_one(int arr[], int size) सरणी लेता है और केवल 0 के साथ उपसरणियों की संख्या और केवल 1 के साथ उपसरणियों की संख्या देता है।
-
उप-सरणी के लिए प्रारंभिक गणनाएं temp_0 और temp_1 के रूप में लें।
-
0 और 1 की अस्थायी लगातार गणनाओं को count_0 और count_1 के रूप में लें।
-
हम लूप के लिए i=0 से I
-
यदि वर्तमान तत्व 0 वेतन वृद्धि count_0 है।
-
यदि नहीं, तो सभी संभावित उप-सरणी की गणना करें, जिसमें 0 की संख्या के साथ temp_one_0=count*(count+1)/2.
-
अब तक मिले सभी 0 के साथ उप-सरणी के लिए इसे पिछले temp_0 में जोड़ें।
-
गिनती_1, temp_one_1 औरtemp_1 के रूप में चर के साथ 1 के लिए लूप के लिए एक समान प्रक्रिया करें।
-
दोनों ट्रैवर्सल के अंत में, temp_0 और temp_1 में एआर के भीतर सभी सबएरे की संबंधित संख्या होगी जिसमें सभी 0 और सभी 1 हैं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void sub_zero_one(int arr[], int size){
int count_1 = 0;
int count_0 = 0;
int temp_1 = 0;
int temp_0 = 0;
for (int i = 0; i < size; i++){
if (arr[i] == 1){
count_1++;
}
else{
int temp_one_1 = (count_1) * (count_1 + 1) / 2;
temp_1 = temp_1 + temp_one_1;
count_1 = 0;
}
}
for (int i = 0; i < size; i++){
if (arr[i] == 0)
{ count_0++; }
else{
int temp_one_0 = (count_0) * (count_0 + 1) / 2;
temp_0 = temp_0 + temp_one_0;
count_0 = 0;
}
}
if (count_1){
int temp_one_1 = (count_1) * (count_1 + 1) / 2;
temp_1 = temp_1 + temp_one_1;
}
if (count_0){
int temp_one_0 = (count_0) * (count_0 + 1) / 2;
temp_0 = temp_0 + temp_one_0;
}
cout<<"Subarrays with only 0's are : "<<temp_0;
cout<<"\nSubarrays with only 1's are : "<<temp_1;
}
int main(){
int arr[] = { 0, 0, 0, 1, 1, 0, 1};
int size = sizeof(arr) / sizeof(arr[0]);
sub_zero_one(arr, size);
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Subarrays with only 0's are : 7 Subarrays with only 1's are : 4