Find number of subarrays with even length

Array, Iterative approach

Given an array, return sum of all subarrays with even length.

Solutions

The algorithm you provided is calculating the sum of all subarrays with even length 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 length 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 EvenLengthSubarraysSum is defined with one parameter, arr, which is the input array. A variable result is initialized to 0. This variable will hold the sum of all subarrays with even length.

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 arr[i]. This variable will hold the sum of the subarray starting from index i.

3. Inner Loop: The inner loop starts from i+1 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 Length: After extending the subarray, it checks if the length of the subarray is even. This is done by checking if (i+j+1) % 2 == 0. If the length is even, it adds sum to result.

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

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

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

        return result;
    }

}

Complexity

• Time complexity: O(N^2)

• Space complexity: O(1)