CountSubArray

package Countsubarraywithequalzeroandone;

import java.util.HashMap;
//The idea is assume 0s as -1 and 1 as 1 itself and calculate the sum . For equal no of 0s and 1s always this way sum wud be zero .so we need to check the element if is 0 add -1 if its is 1 add +1.
//Initially take sum as 0 and put in map with key equal to sum 0 and value 1.
//Take a variable to hold cumulative sum of no of sub array.
public class CountSubArray {
    public static void main(String as[]) {
        //int arr[] = {1,0,0,1,0,1,1};// ans will be 8
        //int arr[] = {1,0,0,1,};//ans will be 3
        //int arr[] = {1,0,1,};//ans will be 2
        int arr[] = {1,0};//ans will be 1
        int countSubArray = countSubArray(arr);
       System.out.println("Total number of sub array :"+countSubArray);
    }

    private static int countSubArray(int[] arr) {
        int sum = 0;//initially , before processing any element of the array lets take sum as 0 and put in hashmap with frequency as 1
          //Start processing each     //1,      0,        0,        1,       0,          1,         1
          //sum                       //0+1=1   1+-1=0   0+-1=-1    -1+1=0   0+-1=-1     -1+1=0    0+1=1
          //sum                        1,        0,      -1,         0,      -1,          0,       1
          //frequency                  1          1       1           2       2           3        2
          //Now consider sum&frequency from left to right
          // 0 came twice at 3rd index so
          //  --------
          //   1     0 's sum is 1 and
          //   -----------------------
          //   1     0       0       1 's sum is also 1 which means
          //                 ------------
          //                 0         1 will be one sub array and it is having equal no of 1 and 0 ie why we can conclude that if for any element the frequency comes out as 2 there must be one subarry with equal 0s and 1s
          // In general we can say if frequency comes out to be 'n' for a particular sum of the elements at any position then total no pf sub array present TILL** that position in an array of 0 and 1's will be n-1.
          // And as we continue to put sum in map so once a sum is already there we can retrieve that and keep on adding it to our ans to find total no of array .
          // In code logic is like  for a map,  map.get(sum) which returns the frequency before incremented inside if(map.contains(sum)){ans=ans+map.get(sum); map.put(sum,map.get(sum)+1)}
          // In above explanation map.get(sum)+1 is like value of 'n' and  map.get(sum) is like value of 'n-1'
          // ans =ans+map.get(sum) will be like , keep on adding the sub arrays of 0s and 1s present. Once for loop exists returns the ans.
        int ans = 0; //will hold cumulative sum of all the sub array.
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);//put sum 0 first time in map.
        for (int i = 0; i < arr.length; i++) {
            //consider 0 as -1 and 1 as 1
            if (arr[i] == 0) {
                sum += -1;
            } else if (arr[i] == 1) {
                sum = sum + 1;
            }
            if (map.containsKey(sum)) {
                ans = ans + map.get(sum); //cumulative sum of all the sub arrays of equal no of 1s and 0s.
                map.put(sum, map.get(sum) + 1); //increase the frequency by 1
            } else {
                map.put(sum, 1);
            }

        }
        return ans;
    }

}