Techno Blender
Digitally Yours.
0 19

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.

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).

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.

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).