Given a binary array consisting of only zeroes and ones. The task is to find:
- The number of subarrays which has only 1 in it.
- The number of subarrays which has only 0 in it.
Examples:
Input: arr[] = {0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1}
Output:
The number of subarrays consisting of 0 only: 7
The number of subarrays consisting of 1 only: 7Input: arr[] = {1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1}
Output:
The number of subarrays consisting of 0 only: 5
The number of subarrays consisting of 1 only: 15
Naive Approach-
The idea is to find all subarray and count how many subarrays contain only 1 and how many subarrays contain only 0.
Steps to implement-
- Initialize count0=0 to store the number of subarrays which has only 0 in it.
- Initialize count1=0 to store the number of subarrays which has only 1 in it.
- Run two loops to find all subarrays
- Then check if any subarray has 0 only then increment count0 by 1
- Then check if any subarray has 1 only then increment count1 by 1
Code-
C++
// C++ program to count the number of subarrays// that having only 0's and only 1's#include <bits/stdc++.h>using namespace std;// Function to count number of subarraysvoid countSubarraysof1and0(int arr[], int N){ //To store count of subarray containing 0 only int count0=0; //To store count of subarray containing 1 only int count1=0; //Find all subarray for(int i=0;i<N;i++){ for(int j=i;j<N;j++){ //To tell whether this subarray contains all 0 bool val1=false; //To tell whether this subarray contains all 1 bool val2=false; //Check whether this subarray contains all 0 int k=i; while(k<=j){ if(arr[k]!=0){break;} k++; } if(k==j+1){val1=true;} //Check whether this subarray contains all 1 k=i; while(k<=j){ if(arr[k]!=1){break;} k++; } if(k==j+1){val2=true;} //When subarray conatins all 0 if(val1==true){count0++;} //when subarray contains all 1 if(val2==true){count1++;} } } cout << "Count of subarrays of 0 only: " << count0<<endl; cout << "Count of subarrays of 1 only: " << count1<<endl; }// Driver Codeint main(){ int arr[] = { 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1 }; int N = sizeof(arr) / sizeof(arr[0]); countSubarraysof1and0(arr, N); return 0;} |
Java
import java.util.Scanner;public class Main { // Function to count number of subarrays static void countSubarraysof1and0(int[] arr, int N) { // To store count of subarray containing 0 only int count0 = 0; // To store count of subarray containing 1 only int count1 = 0; // Find all subarrays for (int i = 0; i < N; i++) { for (int j = i; j < N; j++) { // To tell whether this subarray contains all 0 boolean val1 = false; // To tell whether this subarray contains all 1 boolean val2 = false; // Check whether this subarray contains all 0 int k = i; while (k <= j) { if (arr[k] != 0) { break; } k++; } if (k == j + 1) { val1 = true; } // Check whether this subarray contains all 1 k = i; while (k <= j) { if (arr[k] != 1) { break; } k++; } if (k == j + 1) { val2 = true; } // When subarray contains all 0 if (val1) { count0++; } // When subarray contains all 1 if (val2) { count1++; } } } System.out.println("Count of subarrays of 0 only: " + count0); System.out.println("Count of subarrays of 1 only: " + count1); } // Driver Code public static void main(String[] args) { int[] arr = { 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1 }; int N = arr.length; countSubarraysof1and0(arr, N); }} |
Python
# Function to count the number of subarrays containing 0's and 1'sdef countSubarraysOf1And0(arr): N = len(arr) # To store the count of subarrays containing 0 only count0 = 0 # To store the count of subarrays containing 1 only count1 = 0 # Find all subarrays for i in range(N): for j in range(i, N): # To tell whether this subarray contains all 0 val1 = True # To tell whether this subarray contains all 1 val2 = True # Check whether this subarray contains all 0 for k in range(i, j + 1): if arr[k] != 0: val1 = False break # Check whether this subarray contains all 1 for k in range(i, j + 1): if arr[k] != 1: val2 = False break # When the subarray contains all 0 if val1: count0 += 1 # When the subarray contains all 1 if val2: count1 += 1 print("Count of subarrays of 0 only:", count0) print("Count of subarrays of 1 only:", count1)# Driver Codeif __name__ == "__main__": arr = [1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1] countSubarraysOf1And0(arr) |
C#
using System;namespace CountSubarraysOfOnesAndZeros{ class Program { static void CountSubarraysOf1And0(int[] arr, int N) { // To store count of subarray containing 0 only int count0 = 0; // To store count of subarray containing 1 only int count1 = 0; // Find all subarrays for (int i = 0; i < N; i++) { for (int j = i; j < N; j++) { // To tell whether this subarray contains all 0 bool val1 = false; // To tell whether this subarray contains all 1 bool val2 = false; // Check whether this subarray contains all 0 int k = i; while (k <= j) { if (arr[k] != 0) { break; } k++; } if (k == j + 1) { val1 = true; } // Check whether this subarray contains all 1 k = i; while (k <= j) { if (arr[k] != 1) { break; } k++; } if (k == j + 1) { val2 = true; } // When subarray contains all 0 if (val1 == true) { count0++; } // When subarray contains all 1 if (val2 == true) { count1++; } } } Console.WriteLine($"Count of subarrays of 0 only: {count0}"); Console.WriteLine($"Count of subarrays of 1 only: {count1}"); } static void Main(string[] args) { int[] arr = { 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1 }; int N = arr.Length; CountSubarraysOf1And0(arr, N); } }} |
Javascript
// Function to count the number of subarrays// that contain only 0's and only 1'sfunction countSubarraysOf1And0(arr) { // Initialize counters for subarrays with all 0's and all 1's let count0 = 0; let count1 = 0; // Find all subarrays for (let i = 0; i < arr.length; i++) { for (let j = i; j < arr.length; j++) { // To tell whether this subarray contains all 0's let val1 = false; // To tell whether this subarray contains all 1's let val2 = false; // Check whether this subarray contains all 0's let k = i; while (k <= j) { if (arr[k] !== 0) { break; } k++; } if (k === j + 1) { val1 = true; } // Check whether this subarray contains all 1's k = i; while (k <= j) { if (arr[k] !== 1) { break; } k++; } if (k === j + 1) { val2 = true; } // When the subarray contains all 0's if (val1) { count0++; } // When the subarray contains all 1's if (val2) { count1++; } } } console.log("Count of subarrays of 0 only: " + count0); console.log("Count of subarrays of 1 only: " + count1);}// Driver Codeconst arr = [1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1];countSubarraysOf1And0(arr); |
Output
Count of subarrays of 0 only: 5 Count of subarrays of 1 only: 15
Time Complexity: O(N3), because of two loops to find all subarrays and the third loop is to find which subarray contains only 1 and which subarray contains only 0
Auxiliary Space: O(1), because no extra space has been used
Approach: To count 1’s, the idea is to start traversing the array using a counter. If the current element is 1, increment the counter otherwise add counter*(counter+1)/2 to the number of subarrays and reinitialize counter to 0. Similarly, find the number of subarrays with only 0’s in it.
Below is the implementation of the above approach:
C++
// C++ program to count the number of subarrays// that having only 0's and only 1's#include <bits/stdc++.h>using namespace std;// Function to count number of subarraysvoid countSubarraysof1and0(int a[], int n){ int count1 = 0, count0 = 0; int number1 = 0, number0 = 0; // Iterate in the array to find count for (int i = 0; i < n; i++) { // check if array element // is 1 or not if (a[i] == 1) { count1 ++; number0 += (count0) * (count0 + 1) / 2; count0 = 0; } //if element is 0 else { count0++; number1 += (count1) * (count1 + 1) / 2; count1 = 0; } } // After iteration completes, // check for the last set of subarrays if (count1) number1 += (count1) * (count1 + 1) / 2; if (count0) number0 += (count0) * (count0 + 1) / 2; cout << "Count of subarrays of 0 only: " << number0; cout << "\nCount of subarrays of 1 only: " << number1;}// Driver Codeint main(){ int a[] = { 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1 }; int n = sizeof(a) / sizeof(a[0]); countSubarraysof1and0(a, n); return 0;} |
Java
// Java program to count the number of subarrays// that having only 0's and only 1'simport java.io.*;class GFG { // Function to count number of subarraysstatic void countSubarraysof1and0(int a[], int n){ int count1 = 0, count0 = 0; int number1 = 0, number0 = 0; // Iterate in the array to find count for (int i = 0; i < n; i++) { // check if array element // is 1 or not if (a[i] == 1) { count1 += 1; number0 += (count0) * (count0 + 1) / 2; count0 = 0; } else { count0++; number1 += (count1) * (count1 + 1) / 2; count1 = 0; } } // After iteration completes, // check for the last set of subarrays if (count1>0) number1 += (count1) * (count1 + 1) / 2; if (count0>0) number0 += (count0) * (count0 + 1) / 2; System.out.println("Count of subarrays of 0 only: " + number0); System.out.println( "\nCount of subarrays of 1 only: " + number1);}// Driver Code public static void main (String[] args) { int a[] = { 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1 }; int n = a.length; countSubarraysof1and0(a, n);; }}// This code is contributed by inder_verma.. |
Python3
# Python 3 program to count the number of # subarrays that having only 0's and only 1's# Function to count number of subarraysdef countSubarraysof1and0(a, n): count1 = 0 count0 = 0 number1 = 0 number0 = 0 # Iterate in the array to find count for i in range(0, n, 1): # check if array element is 1 or not if (a[i] == 1): number0 += ((count0) * (count0 + 1) / 2) count0 = 0 count1 += 1 else: number1 += ((count1) * (count1 + 1) / 2) count1 = 0 count0 += 1 # After iteration completes, # check for the last set of subarrays if (count1): number1 += (count1) * (count1 + 1) / 2 if (count0): number0 += (count0) * (count0 + 1) / 2 print("Count of subarrays of 0 only:", int(number0)) print("Count of subarrays of 1 only:", int(number1))# Driver Codeif __name__ == '__main__': a = [1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1] n = len(a) countSubarraysof1and0(a, n)# This code is contributed by# Surendra_Gangwar |
C#
// C# program to count the number of subarrays// that having only 0's and only 1'susing System;class GFG { // Function to count number of subarraysstatic void countSubarraysof1and0(int []a, int n){ int count1 = 0, count0 = 0; int number1 = 0, number0 = 0; // Iterate in the array to find count for (int i = 0; i < n; i++) { // check if array element // is 1 or not if (a[i] == 1) { count1 += 1; number0 += (count0) * (count0 + 1) / 2; count0 = 0; } else { number1 += (count1) * (count1 + 1) / 2; count1 = 0; count0++; } } // After iteration completes, // check for the last set of subarrays if (count1>0) number1 += (count1) * (count1 + 1) / 2; if (count0>0) number0 += (count0) * (count0 + 1) / 2; Console.WriteLine("Count of subarrays of 0 only: " + number0); Console.WriteLine( "\nCount of subarrays of 1 only: " + number1);}// Driver Code public static void Main () { int []a = { 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1 }; int n = a.Length; countSubarraysof1and0(a, n);; }}// This code is contributed by inder_verma.. |
Javascript
<script>// Javascript program to count the number of subarrays// that having only 0's and only 1's // Function to count number of subarraysfunction countSubarraysof1and0(a, n){ let count1 = 0, count0 = 0; let number1 = 0, number0 = 0; // Iterate in the array to find count for (let i = 0; i < n; i++) { // check if array element // is 1 or not if (a[i] == 1) { count1 += 1; number0 += (count0) * (count0 + 1) / 2; count0 = 0; } else { number1 += (count1) * (count1 + 1) / 2; count1 = 0; count0 += 1; } } // After iteration completes, // check for the last set of subarrays if (count1>0) number1 += (count1) * (count1 + 1) / 2; if (count0>0) number0 += (count0) * (count0 + 1) / 2; document.write("Count of subarrays of 0 only: " + number0 + "<br/>"); document.write( "\nCount of subarrays of 1 only: " + number1);} // driver program let a = [ 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1 ]; let n = a.length; countSubarraysof1and0(a, n); </script> |
PHP
<?php// PHP program to count the number // of subarrays that having only // 0's and only 1's// Function to count number of subarraysfunction countSubarraysof1and0($a, $n){ $count1 = 0; $count0 = 0; $number1 = 0; $number0 = 0; // Iterate in the array to find count for ($i = 0; $i <$n; $i++) { // check if array element // is 1 or not if ($a[$i] == 1) { $count1 += 1; $number0 += ($count0) * ($count0 + 1) / 2; $count0 = 0; } else { $number1 += ($count1) * ($count1 + 1) / 2; $count1 = 0; $count0 += 1; } } // After iteration completes, // check for the last set of subarrays if ($count1) $number1 += ($count1) * ($count1 + 1) / 2; if ($count0) $number0 += ($count0) * ($count0 + 1) / 2; echo "Count of subarrays of 0 only: " , $number0; echo "\nCount of subarrays of 1 only: " , $number1;}// Driver Code$a = array( 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1 );$n = count($a);countSubarraysof1and0($a, $n);// This code is contributed by inder_verma?> |
Output
Count of subarrays of 0 only: 5 Count of subarrays of 1 only: 15
Complexity Analysis
- Time Complexity: O(N)
- Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
