Print number of even sum sub-arrays of an array

Share

Problem: For a given array of positive or negative integers, find count of sub-arrays whose sum is even.

Problem Explanation: For a given array a ={1, -2, 3, 4, -5},  even sum sub-arrays are {-2}, {3, 4, -5}, {-2 , 3, 4, -5}, {4}, {1, -2, 3}, {1, -2, 3, 4}. Hence, output will be 6.

Java Implementation

public int evenSumSubArrays(int arr[]) {
    int[] count = new int[2];
    int sum = 0;

    for (int i = 0; i < arr.length; i++) {
        sum = (sum + arr[i]) % 2;
        count[Math.abs(sum)]++;
    }

    //Total even sum arrays = Total even sub arrays + number of odd pairs 
                                            //+ number of even only pairs
    int totalEvenSumSubArrayCount = count[0] + (count[0] 
                                    * (count[0] - 1) / 2)  
                                    + (count[1] * (count[1] - 1) / 2);

    return (totalEvenSumSubArrayCount); 
}

TimeComplexity: O(n)

Note: If you find any other better way to approach to this problem or you find any issue/error in above code snippets/approaches – please share it in the comments section below and get a chance to enrol free of cost for an online Live Data Structure and Algorithm course (specially designed for interview preparation for software companies like Amazon, Google, Facebook, FlipKart, SnapDeal, HealthKart…)