# Subarray with equal occurrences

Posted: 5 Nov, 2020

Difficulty: Moderate

#### You have been given an array/list ARR of length N consisting of 0s and 1s only. Your task is to find the number of subarrays(non-empty) in which the number of 0s and 1s are equal.

##### Input Format:

```
The first line contains an integer 'T' denoting the number of test cases. Then each test case follows.
The first line of each test case contains a positive integer ‘N’ which represents the length of the array/list.
The second line of each test case contains ‘N’ single space-separated integers representing the elements of the array/list.
```

##### Output Format:

```
For each test case, the only line of output will print the number of subarrays in which the number of 0s and 1s are equal.
Print the output of each test case in a separate line.
```

#### Note:

```
You are not required to print the expected output; it has already been taken care of. Just implement the function.
```

##### Constraints:

```
1 <= T <= 100
1 <= N <= 5 * 10^3
0 <= ARR[i] <= 1
Time limit: 1 sec
```

Approach 1

Approach 2

If we consider every ‘0’ as -1, then a subarray containing equal 0s and 1s will give a sum of 0. So, we can use the * cumulative sum* to count these subarrays with sum 0 easily.

**The idea is based on the fact that if a ****cumulative sum**** appears again in the array, then the subarray between these two occurrences of ****cumulative sum****, will have a sum of 0.**

For example-

Given ARR = [1, 1, 1, 0, 0, 1]

Cumu. Sum = [1, 2, 3, 2, 1, 2]

Here, one of the required subarrays has index range[1, 4]. We can see that 1 appears again in the cumulative sum at index 4 (previously at index 0). Hence, the subarray between index 0(exclusive) and index 4(inclusive) is one of the subarrays with equal 0s and 1s.

Here is the algorithm:

- We will maintain ‘
*RESULT*’ to count subarrays with equal 0s and 1s. - We will initialise ‘
*CUMULATIVE’*to 0 to store the cumulative sum. - Declare a hashtable ‘
*FREQUENCY*’ that stores the frequency of the cumulative sum.- Initialise FREQUENCY[0] by 1 as the cumulative sum of the empty array is 0.

- Now start iterating over the array and calculate the cumulative sum.
- If ARR[i] == 1, we increment ‘
*CUMULATIVE*’ by 1. - Else, we decrement it by 1.
- Add
*FREQUENCY[CUMULATIVE]*to*RESULT*. This is because the total subarrays ending on the current element with sum 0 is given by*FREQUENCY[CUMULATIVE].* - Increment
*FREQUENCY[CUMULATIVE]*by 1.

- If ARR[i] == 1, we increment ‘

SIMILAR PROBLEMS

# Vertical Sum in BST

Posted: 27 Jul, 2021

Difficulty: Moderate

# Remove K Corner Elements

Posted: 31 Jul, 2021

Difficulty: Easy

# Wildcard Queries

Posted: 31 Jul, 2021

Difficulty: Hard

# Matching Prefix

Posted: 21 Aug, 2021

Difficulty: Moderate

# Connecting Ropes

Posted: 12 Nov, 2021

Difficulty: Hard