हमें एक सरणी arr[] दी गई है जिसमें केवल 0's और 1's हैं। लक्ष्य arr[] के उन सभी सबएरे की गिनती करना है जिनमें केवल 0's हों या केवल 1's हों, दोनों नहीं। यदि सरणी [1,0,0] है। सबएरे होंगे 0's के लिए केवल [0], [0], [0,0] और 1's के लिए केवल [1]।
उदाहरण सहित समझ
इनपुट - arr[] = { 0, 0, 1, 1, 1, 0 };
आउटपुट - केवल 0's वाले सबएरे: 4, केवल 1's वाले सबएरे: 6
व्याख्या - सबएरे होंगे:
सभी 0's के लिए: [0], [0], [0], [0,0]. कुल 4 (arr[0], arr[1], arr[5], arr[0-1]) सभी 1's के लिए: [1], [1], [1], [1,1], [1,1], [1,1,1]. कुल 6 (arr[2], arr[2], arr[4], arr[2-3], arr[3-4], arr[2-4])
इनपुट - arr[] = { 1,0,1,0 };
आउटपुट - केवल 0's वाले सबएरे: 2, केवल 1's वाले सबएरे: 2
व्याख्या - सबएरे होंगे:
सभी 0's के लिए: [0], [0]. कुल 2 (arr[1], arr[3]) सभी 1's के लिए: [1], [1]. कुल 2 (arr[0], arr[2])
प्रोग्राम में उपयोग किया गया दृष्टिकोण
हम सरणी में लगातार 0's और 1's की गिनती के लिए अलग-अलग काउंटर count_0 और count_1 लेकर सरणी को दो बार ट्रैवर्स करेंगे। ऐसी प्रत्येक गिनती के लिए, संभावित सबएरे होंगे count_0*(count_0+1)/2 और इसी तरह count_1 के लिए।
इसे कुल total_0 काउंट में जोड़ें जब तक सरणी का अंत नहीं पहुंच जाता। 1's के लिए समान प्रक्रिया करें।
- संख्याओं की एक सरणी
arr[]लें। - फंक्शन
sub_zero_one(int arr[], int size)सरणी लेता है और केवल 0's वाले सबएरे की गिनती और केवल 1's वाले सबएरे की गिनती लौटाता है। - सबएरे के लिए प्रारंभिक काउंट
temp_0औरtemp_1के रूप में लें। - लगातार 0's और 1's की अस्थायी गिनती
count_0औरcount_1के रूप में लें। - फॉर लूप का उपयोग करके i=0 से i<size तक सरणी को ट्रैवर्स करें।
- यदि वर्तमान तत्व 0 है तो
count_0बढ़ाएँ। - यदि नहीं, तो
count_0संख्या के 0's के साथ सभी संभावित सबएरे की गणना करें:temp_one_0 = count * (count + 1) / 2। - इसे अब तक मिले सभी 0's वाले सबएरे के पिछले
temp_0में जोड़ें। count_1,temp_one_1औरtemp_1चर के साथ 1's के लिए समान प्रक्रिया फॉर लूप का उपयोग करके करें।- दोनों ट्रैवर्सल के अंत में,
temp_0औरtemp_1में क्रमशःarrके भीतर उन सभी सबएरे की संख्या होगी जिनमें सभी 0's और सभी 1's हैं।
उदाहरण
#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
