Given an array arr[] of length N of 0’s and 1’s, the task is to find the total number of subarrays of 0’s.
Examples:
Input: N = 4, arr[] = {0, 0, 1, 0}
Output: 4
Explanation: Following are the subarrays of length 1: {0}, {0}, {0} – 3 length 2: {0, 0} – 1. Total Subarrays: 3 + 1 = 4Input: N = 4, arr[] = {0, 0, 0, 0}
Output: 10
Explanation: The following are the subarrays of
- length 1: {0}, {0}, {0}, {0} = 4
- length 2: {0, 0}, {0, 0}, {0, 0} = 3
- length 3: {0, 0, 0}, {0, 0, 0} = 2
- length 4: {0, 0, 0, 0} = 1
Total Subarrays: 4 + 3 + 2 + 1 = 10
Approach: To solve the problem follow the below idea:
The concept is that if there are n consecutive 0s, then there are ((n+1) * (n))/2 total 0 subarrays.
Steps involved in the implementation of code:
- Maintain a variable for the response, initialize it with 0, and another variable for the counter, which keeps track of the number of continuous 0s.
- Start a for loop and traverse through the array.
- Count the number of contiguous zeros.
- Including count*(count+1)/2 in the solution because count*(count+1)/2 subarrays can be produced using the count number of continuous zeros.
- Add count*(count+1)/2 to the answer if the count is more than zero.
- Return the answer.
Below is the code implementation of the above approach:
C++14
// C++ Implementation of approach#include <bits/stdc++.h>using namespace std;// Function to count the// number of subarrayslong long no_of_subarrays(int N, int arr[]){ long long count = 0, answer = 0; // Loop through the array for (int i = 0; i < N; i++) { // If the element is 0, // increment the count if (arr[i] == 0) { count++; } // If the element is not 0, // calculate the number of // subarrays that can be formed // with the previous 0's else { answer += ((count * (count + 1)) / 2); count = 0; } } // Calculate the number of // subarrays that can be formed // with any remaining 0's answer += ((count * (count + 1)) / 2); return answer;}// Driver codeint main(){ int arr[] = { 0, 0, 1, 0 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call long long result = no_of_subarrays(N, arr); cout << result << endl; return 0;} |
Java
// Java Implementation of approachimport java.util.*;public class GFG { // Function to count the // number of subarrays static long no_of_subarrays(int N, int[] arr) { long count = 0, answer = 0; // Loop through the array for (int i = 0; i < N; i++) { // If the element is 0, // increment the count if (arr[i] == 0) { count++; } // If the element is not 0, // calculate the number of // subarrays that can be formed // with the previous 0's else { answer += ((count * (count + 1)) / 2); count = 0; } } // Calculate the number of // subarrays that can be formed // with any remaining 0's answer += ((count * (count + 1)) / 2); return answer; } // Driver code public static void main(String[] args) { int[] arr = { 0, 0, 1, 0 }; int N = arr.length; // Function call long result = no_of_subarrays(N, arr); System.out.println(result); }} |
Python3
def no_of_subarrays(N, arr): count = 0 answer = 0 # Loop through the array for i in range(N): # If the element is 0, # increment the count if arr[i] == 0: count += 1 # If the element is not 0, # calculate the number of # subarrays that can be formed # with the previous 0's else: answer += (count * (count + 1)) // 2 count = 0 # Calculate the number of # subarrays that can be formed # with any remaining 0's answer += (count * (count + 1)) // 2 return answer# Driver codearr = [0, 0, 1, 0]N = len(arr)# Function callresult = no_of_subarrays(N, arr)print(result)#This code is contributed bY Akash Jha |
C#
// C# code implementation of the above approachusing System;public class GFG { // Function to count the number of subarrays static long no_of_subarrays(int N, int[] arr) { long count = 0, answer = 0; // Loop through the array for (int i = 0; i < N; i++) { // If the element is 0, increment the count if (arr[i] == 0) { count++; } // If the element is not 0, calculate the number // of subarrays that can be formed with the // previous 0's else { answer += ((count * (count + 1)) / 2); count = 0; } } // Calculate the number of subarrays that can be // formed with any remaining 0's answer += ((count * (count + 1)) / 2); return answer; } static public void Main() { // Code int[] arr = { 0, 0, 1, 0 }; int N = arr.Length; // Function call long result = no_of_subarrays(N, arr); Console.WriteLine(result); }}// This code is contributed by karthik. |
Javascript
function no_of_subarrays(N, arr) { let count = 0; let answer = 0; // Loop through the array for (let i = 0; i < N; i++) { // If the element is 0, // increment the count if (arr[i] == 0) { count++; } // If the element is not 0, // calculate the number of // subarrays that can be formed // with the previous 0's else { answer += ((count * (count + 1)) / 2); count = 0; } } // Calculate the number of // subarrays that can be formed // with any remaining 0's answer += ((count * (count + 1)) / 2); return answer;}// Driver codeconst arr = [0, 0, 1, 0];const N = arr.length;// Function callconst result = no_of_subarrays(N, arr);console.log(result);// This code is contributed by Akash Jha |
Output
4
Time Complexity: O(N).
Auxiliary Space: O(1).
Approach 2: Sliding Window
Implementation :
C++
#include <iostream>#include <vector>int GFG(std::vector<int>& arr) { int count = 1; int start = 2; int end = 0; int n = arr.size(); while (end < n) { if (arr[end] == 0) { count++; } else { start = end + 1; } end++; } return count;}int main() { std::vector<int> arr = {0, 0, 0, 0, 0}; int result = GFG(arr); std::cout << "Total number of subarrays of 0's: " << result << std::endl; return 0;} |
Java
import java.util.ArrayList;import java.util.List;public class Main { // Function to count the total number of subarrays of 0's public static int GFG(List<Integer> arr) { // Initialize count to 1 int count = 1; // Initialize start to 2 int start = 2; // Initialize end to 0 int end = 0; // Get the size of the array int n = arr.size(); // Iterate through the array while (end < n) { // If the current element is 0, increment count if (arr.get(end) == 0) { count++; } // If the current element is not 0, update start else { start = end + 1; } // Move to the next element end++; } // Return the total count return count; } public static void main(String[] args) { // Create an array and initialize it with 0's List<Integer> arr = new ArrayList<>(); arr.add(0); arr.add(0); arr.add(0); arr.add(0); arr.add(0); // Call the GFG function to count the subarrays of 0's int result = GFG(arr); // Print the result System.out.println("Total number of subarrays of 0's: " + result); }} |
Python
# Function to count the total number of subarrays of 0'sdef GFG(arr): # Initialize count to 1 count = 1 # Initialize start to 2 start = 2 # Initialize end to 0 end = 0 # Get the size of the array n = len(arr) # Iterate through the array while end < n: # If the current element is 0, increment count if arr[end] == 0: count += 1 # If the current element is not 0, update start else: start = end + 1 # Move to the next element end += 1 # Return the total count return count# Create an array and initialize it with 0'sarr = [0, 0, 0, 0, 0]# Call the GFG function to count the subarrays of 0'sresult = GFG(arr)# Print the resultprint("Total number of subarrays of 0's:", result) |
C#
using System;using System.Collections.Generic;public class Program{ // Function to count the total number of subarrays of 0's public static int GFG(List<int> arr) { // Initialize count to 1 int count = 1; // Initialize end to 0 int end = 0; // Get the size of the list int n = arr.Count; // Iterate through the list while (end < n) { // If the current element is 0, increment count if (arr[end] == 0) { count++; } end++; } // Return the total count return count; } public static void Main(string[] args) { // Create a list and initialize it with 0's List<int> arr = new List<int> { 0, 0, 0, 0, 0 }; // Call the GFG function to count the subarrays of 0's int result = GFG(arr); // Print the result Console.WriteLine("Total number of subarrays of 0's: " + result); }} |
Javascript
// Function to count the total number of subarrays of 0'sfunction GFG(arr) { // Initialize count to 1 let count = 1; // Initialize start to 2 let start = 2; // Initialize end to 0 let end = 0; // Get the size of the array const n = arr.length; // Iterate through the array while (end < n) { // If the current element is 0, increment count if (arr[end] === 0) { count++; } else { start = end + 1; // If the current element is not 0, update start } end++; } // Return the total count return count;}function main() { const arr = [0, 0, 0, 0, 0]; const result = GFG(arr); console.log(`Total number of subarrays of 0's: ${result}`);}main(); |
Output
Total number of subarrays of 0's: 6
Take a part in the ongoing discussion
