Find number of subarrays with even sum - GeeksforGeeks

Find number of subarrays with even sum - GeeksforGeeks
Given an array, find the number of subarrays whose sum is even.

O(n) Time and O(1) Space Method [Efficient]
If we do compute the cumulative sum array in temp[] of our input array, then we can see that the sub-array starting from i and ending at j, has an even sum if temp[] if (temp[j] – temp[i]) % 2 = 0. So, instead of building a cumulative sum array we build a cumulative sum modulo 2 array, and find how many times 0 and 1 appears in temp[] array using handshake formula. [n * (n-1) /2]

int countEvenSum(int arr[], int n)

{

    // A temporary array of size 2. temp[0] is

    // going to store count of even subarrays

    // and temp[1] count of odd.

    // temp[0] is initialized as 1 because there

    // a single even element is also counted as

    // a subarray

    int temp[2] = {1, 0};

 

    // Initialize count.  sum is sum of elements

    // under modulo 2 and ending with arr[i].

    int result = 0, sum = 0;

 

    // i'th iteration computes sum of arr[0..i]

    // under modulo 2 and increments even/odd count

    // according to sum's value

    for (int i=0; i<=n-1; i++)

    {

        // 2 is added to handle negative numbers

        sum = ( (sum + arr[i]) % 2 + 2) % 2;

 

        // Increment even/odd count

        temp[sum]++;

    }

 

    // Use handshake lemma to count even subarrays

    // (Note that an even cam be formed by two even

    // or two odd)

    result = result + (temp[0]*(temp[0]-1)/2);

    result = result + (temp[1]*(temp[1]-1)/2);

 

    return (result);

}

O(n²) time and O(1) space method [Brute Force]
We can simply generate all the possible sub-arrays and find whether the sum of all the elements in them is an even or not. If it is even then we will count that sub-array otherwise neglect it.

int countEvenSum(int arr[], int n)

{

    int result = 0;

 

    // Find sum of all subarrays and increment

    // result if sum is even

    for (int i=0; i<=n-1; i++)

    {

        int sum = 0;

        for (int j=i; j<=n-1; j++)

        {

            sum = sum + arr[j];

            if (sum % 2 == 0)

                    result++;

        }

    }

 

    return (result);

}

Read full article from Find number of subarrays with even sum - GeeksforGeeks