Approach
Step 1: All 0's in arr[] should be treated as -1.
Step 2: The count of each sum[i] value, where sum[i] = sum(arr[0]+..+arr[i]), for I = 0 to n-1, should be stored in a hash table.
Step 3: Once the cumulative sum has been calculated, an incremental count of 1 will be returned as an index in the hash table. A continuous range with an equal number of 1's and 0's is formed by arrays of every pair of positions having the same value in the cumulative sum.
Step 4: Calculate the frequency of each element in the hash table by traversing it now. Let's call the frequency symbol freq. There are (freq * (freq - 1)) / 2 ways to choose any two pairs of indices from a sub-array for every freq > 1. The number of all possible sub-arrays containing an equal number of 1's and 0's will be obtained by repeating the procedure for each frequency and adding the results.
The hash table should also include the frequency of the sum of 0 for the final result.
Explanation
If sum[i] == sum[j], where sum[i] = sum(arr[0]+..+arr[i]) and sum[j] = sum(arr[0]+..+arr[j]), then all 0’s are treated as -1. sum(arr[i+1]+..+arr[j]) must be zero if i is less than "j," otherwise. It can only be 0 if there are exactly as many 1's as 0's in arr(i+1,.., j).
C++ Code
#include <bits/stdc++.h>
using namespace std;
// function to count subarrays
int count_subarry(int arr[], int n)
{
unordered_map<int, int> m;
int curr_sum = 0;
for (int i = 0; i < n; i++)
{ curr_sum += (arr[i] == 0) ? -1 : arr[i];
m[curr_sum]++;
}
int count = 0;
for (auto it = m.begin(); it != m.end(); it++) {
//If more than one prefix subarrays have a specific sum.
if (it->second > 1)
count += ((it->second * (it->second - 1)) / 2);
}
// Add the subarrays with an equal number of 1s and 0s
// starting with the first element.
if (m.find(0) != m.end())
count + = m[0];
return count;
}
// Driver program to test above
int main()
{
int arr[] = {0, 0, 1, 1, 0};
int n = sizeof(arr) / sizeof(arr[0]);
cout << count_subarry(arr, n);
return 0;
}
You can also try this code with Online C++ Compiler
Output:
4
Time Complexity
O(n), where "n" is the array's total number of elements. We were able to achieve linear time complexity because we used HashMap.
Auxiliary Space
O(n), where "n" is the array's element count. This HashMap achieves linear space complexity because the sum was saved as the key.
You can also read about the Longest Consecutive Sequence.
Frequently Asked Questions
What is subarray?
A subarray is an array that is contained within the parent array. It is a continuous portion of the array.
What is hashing?
The process of mapping keys and values into a hash table using a hash function is known as hashing.
What is the time complexity of the hashing method solution for the problem count of subarrays with equal no. of 1's and 0's?
O(n) will be the worst-case time complexity.
What is the space complexity of the hashing method solution for the problem count of subarrays with equal no. of 1's and 0's?
O(n) will be the worst-case space complexity.
What is a contiguous Subarray?
A contiguous subarray is just a subarray of an array with the requirement that the subarray's elements be in the same exact order as the elements in the parent array.
Also Read - Strong number in c
Conclusion
In this article, we have discussed the famous coding question based on the hash map along with its time and space complexity in detail.
To give an edge to your coding preparation, you can refer to our blog Clone a binary tree with random pointers, and Flattening a Multi-level Linked List(Depth Wise). You can also refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, React, JavaScript, System Design, etc.
Recommended Problems -
117+ registered 