Subarray with equal occurrences

Moderate

0/80

Average time to solve is 15m

18 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
7
1 0 0 1 0 1 1 
5
0 0 0 0 0

Sample output 1:

8
0

Explanation of Sample output 1:

For the first test case, there are such 8 subarrays with index range [0, 1], [2, 3], [0, 3], [3, 4], [4, 5], [2, 5], [0, 5], [1, 6].

For the second test case, there is no such subarray.

Sample Input 2:

2
5
1 1 1 0 1
6
1 1 1 1 1 1

Sample output 2:

2
0

Hint 1

Hint 2

Count the number of 0s and 1s in each subarray.

Approaches (2)

Approach 1

Approach 2

BRUTE FORCE

We will visit every subarray using two nested loops and maintain the count of 0s and 1s for each of them. Count of all the subarrays with equal 0s and 1s will be maintained in a ‘RESULT’ variable.

Time Complexity

O(N ^ 2), where N is the length of the array.

We are visiting every subarray, and the total number of subarrays are (N*(N+1))/2. Hence, the time complexity is O(N ^ 2).

Space Complexity

The space complexity is O(1) as no extra space is used.

(100% EXP penalty)

Subarray with equal occurrences

Console