Count subarrays consisting of only 0’s and only 1’s in a binary array

0 0 11 minutes read

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: 7

Input: 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 subarrays
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 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 Code
int 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's
def 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 Code
if __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's
function 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 Code
const 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(N³), 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 subarrays
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 ++;
            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 Code
int 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's
 
import java.io.*;
 
class GFG {
     
// Function to count number of subarrays
static 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 subarrays
def 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 Code
if __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's
 
using System;
 
class GFG {
     
// Function to count number of subarrays
static 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 subarrays
function 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 subarrays
function 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 zambiatek!