Find number of subarrays with even sum

Array, Iterative approach

Given an array, find the number of subarrays whose sum is even.

Solutions

The algorithm you provided is calculating the sum of all subarrays with even sum in an array. This is done by iterating over the array and for each element, calculating the sum of all subarrays starting from that element. While calculating the sum, it checks if the sum of the current subarray is even. If it is, the sum is added to the total result. This process continues for all elements in the array.

Approach - Iterative Technique

Iterates over the array and for each element, it calculates the sum of all subarrays starting from that element.

Steps

1. Initialization: The function countEvenSum is defined with one parameter, arr, which is the input array. A variable result is initialized to 0. This variable will hold the count of subarrays with an even sum.

2. Outer Loop: The outer loop iterates over each element in the array with i as the index. For each i, it initializes a variable sum to 0. This variable will hold the sum of the subarray starting from index i.

3. Inner Loop: The inner loop starts from i and iterates over the rest of the array with j as the index. For each j, it adds arr[j] to sum, effectively extending the subarray by one element.

4. Check for Even Sum: After extending the subarray, it checks if the sum of the current subarray is even. This is done by checking if sum % 2 == 0. If the sum is even, it increments result by 1.

5. Return Result: After iterating over all elements and all subarrays, it returns result, which is the count of all subarrays with an even sum.

public class Solution
{  
    public int countEvenSum(int[] arr)
    {
        int result = 0;

        for (int i = 0; i < arr.Length; i++)
        {
            int sum = 0;
            for (int j = i; j < arr.Length; j++)
            {
                sum = sum + arr[j];
                if (sum % 2 == 0)
                    result++;
            }
        }

        return result;
    }
 }   

Complexity

• Time complexity: O(N^2)

• Space complexity: O(1)