Count subarrays with equal number of 1 ' s ▁ and ▁ 0' s | C # implementation to count subarrays with equal number of 1 ' s ▁ and ▁ 0' s ; function to count subarrays with equal number of 1 ' s ▁ and ▁ 0' s ; ' um ' implemented as hash table to store frequency of values obtained through cumulative sum ; Traverse original array and compute cumulative sum and increase count by 1 for this sum in ' um ' . Adds ' - 1' when arr [ i ] == 0 ; traverse the hash table ' um ' ; If there are more than one prefix subarrays with a particular sum ; add the subarrays starting from 1 st element and have equal number of 1 ' s ▁ and ▁ 0' s ; required count of subarrays ; Driver program to test above
using System ; using System . Collections . Generic ; class GFG { static int countSubarrWithEqualZeroAndOne ( int [ ] arr , int n ) { Dictionary < int , int > mp = new Dictionary < int , int > ( ) ; int curr_sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { curr_sum += ( arr [ i ] == 0 ) ? - 1 : arr [ i ] ; if ( mp . ContainsKey ( curr_sum ) ) { var v = mp [ curr_sum ] ; mp . Remove ( curr_sum ) ; mp . Add ( curr_sum , ++ v ) ; } else mp . Add ( curr_sum , 1 ) ; } int count = 0 ; foreach ( KeyValuePair < int , int > itr in mp ) { if ( itr . Value > 1 ) count += ( ( itr . Value * ( itr . Value - 1 ) ) / 2 ) ; } if ( mp . ContainsKey ( 0 ) ) count += mp [ 0 ] ; return count ; } public static void Main ( String [ ] args ) { int [ ] arr = { 1 , 0 , 0 , 1 , 0 , 1 , 1 } ; int n = arr . Length ; Console . WriteLine ( " Count ▁ = ▁ " + countSubarrWithEqualZeroAndOne ( arr , n ) ) ; } }