Subarray with equal occurrences

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
CodingNinjas
author
2y

Approach :
1) Convert all 0's to -1's .
2) Now , the questions boils down to finding the number of subarrays with sum=0
3) This is a very standard problem which can be solved in O(N) using Hashing .
4) Ma...read more

CodingNinjas
author
2y
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’ va...read more

CodingNinjas
author
2y
CUMULATIVE SUM METHOD

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...read more

Add answer anonymously...
Amdocs Associate Software Engineer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions
Get AmbitionBox app

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter