Count Of Subarrays With Equal Number Of Zeroes And Ones

faq

1. Why time complexity is O(n)?
Ans ->O(n) where “n” is the number of elements in the array. Because we have used HashMap we are able to achieve linear time complexity.

2. Why space complexity is O(n)?
Ans -> O(n) where “n” is the number of elements in the array. Here in the HashMap we have saved the sum as key, thus linear space complexity is achieved.

3. How to find the smallest subarray having equal number of 0s and 1s?
Ans -> Following the similar to finding the maximum length having equal zeroes and ones, we need to minimise the length.

4. What does the term "Count of Subarray With equal number of zeroes and ones" mean?
Ans -> count Subarrays which contains equal number of zeroes and ones and we need to return its count.

5. What is the Count Of Subarrays With Equal Number Of Zeroes And Ones for arr = {1, 0, 0, 1, 0, 1, 1}
Ans -> Number of subarray = 8
The index range for the 8 sub-arrays are:
(0, 1), (2, 3), (0, 3), (3, 4), (4, 5)
(2, 5), (0, 5), (1, 6)

hints

1.Consider all 0’s in arr[] as -1.
2.Create a hash table that holds the count of each sum[i] value, where sum[i] = sum(arr[0]+..+arr[i]), for i = 0 to n-1.
3.Now start calculating cumulative sum and then we get increment count by 1 for that sum represented as index in the hash table. Sub-array by each pair of positions with same value of cumulative sum constitute a continuous range with equal number of 1’s and 0’s.
4.Now traverse the hash table and get the frequency of each element in the hash table. Let frequency be denoted as freq. For each freq > 1 we can choose any two pair of indices of sub-array by (freq * (freq – 1)) / 2 number of ways . Do the same for all freq and sum up the result that will be the number all possible sub-arrays containing equal number of 1’s and 0’s.
5.Also add freq of the sum 0 in the hash table to the final result.

mcq

1.  What is the average time complexity of this problem?
a) O(n*n)
b) O(n)
c) O(1)
d) None of the above
Ans: b

2. What is the average space complexity of this problem?
a) O(n*n)
b) O(1)
c) O(n)
d) None of the above
Ans: c

3. We will use _______ in this question.
a) Graph
b) Stack
c) Tree
d) Hashing 
Ans: d

4.  What is the Subarray?
a. A subarray is a Subsequence of array.
b. A subarray is a contiguous part of array.
c. Both of the above
d. None of the above

Ans -> b. A subarray is a contiguous part of array.

5. What are the Subarrays of arr = [1,2,3]?
a. [1],[1,2],[1,2,3]
b. [1],[1,2],[1,2,3],[2],[2,3],[3]
c. [1],[1,2],[1,3],[1,2,3],[2],[2,3],[3]
d. None of the above

Ans -> b. [1],[1,2],[1,2,3],[2],[2,3],[3]