Find the total number of Subarrays of 0’s

By Ann Roberts On Mar 19, 2023

Improve Article

Save Article

Like Article

Improve Article

Save Article

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 = 4

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

Java

import java.util.*;

public class GFG {

static long no_of_subarrays(int N, int[] arr)

{

long count = 0, answer = 0;

for (int i = 0; i < N; i++) {

if (arr[i] == 0) {

count++;

}

else {

answer += ((count * (count + 1)) / 2);

count = 0;

}

answer += ((count * (count + 1)) / 2);

return answer;

}

public static void main(String[] args)

{

int[] arr = { 0, 0, 1, 0 };

int N = arr.length;

long result = no_of_subarrays(N, arr);

System.out.println(result);

}

Time Complexity: O(N).
Auxiliary Space: O(1).

Improve Article

Save Article

Like Article

Improve Article

Save Article

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 = 4

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

Java

import java.util.*;

public class GFG {

static long no_of_subarrays(int N, int[] arr)

{

long count = 0, answer = 0;

for (int i = 0; i < N; i++) {

if (arr[i] == 0) {

count++;

}

else {

answer += ((count * (count + 1)) / 2);

count = 0;

}

answer += ((count * (count + 1)) / 2);

return answer;

}

public static void main(String[] args)

{

int[] arr = { 0, 0, 1, 0 };

int N = arr.length;

long result = no_of_subarrays(N, arr);

System.out.println(result);

}

Time Complexity: O(N).
Auxiliary Space: O(1).

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.