Number of Sub-arrays With Odd Sum

class Solution {
public:
    int countSubarrays(vector<int>& data) {
        const int MODULO = 1000000007;
        int result = 0, sum = 0;
        int countOdd = 0, countEven = 1;
    
        for (int value : data) {
            sum += value;
            // Check if the updated sum is even or odd
            if (sum % 2 == 0) {
                result += countOdd;
                countEven++;
            } else {
                result += countEven;
                countOdd++;
            }
            result %= MODULO;  // Ensure the result stays within bounds
        }
    
        return result;
    }
};

The solution involves counting the sub-arrays in a given array where the sum of elements is odd. Written in C++, the approach uses a dynamic programming concept where the cumulative sum of the elements determines the odd and even sub-array counts effectively.

• Begin with initializing the variables:

  • MODULO for bounding the result within the 10^9+7 limit.
  • result to store the number of odd sum sub-arrays.
  • sum to maintain the cumulative sum of the elements.
  • countOdd and countEven to count the occurrences of odd and even sums respectively, initializing countEven to 1 because the sum of an empty sub-array is considered even.

• Iterate through each element in the input vector:

  • Add the current element to the cumulative sum (sum).
  • Decide if sum is even or odd via the modulus operation.
    • If even, add the current count of odd accumulations to result and increment the even count (countEven).
    • If odd, add the current count of even accumulations to result and increment the odd count (countOdd).
  • Apply the MODULO operation to result after each addition to keep it within the specified bounds.

• The function finally returns the result, representing the total count of sub-arrays with odd sums.

This method provides an efficient way to solve the problem by leveraging the properties of cumulative sums with regards to even and odd numbers, facilitating a direct count without needing to generate all sub-arrays explicitly.

class Solution {
    
    public int countSubarraysWithOddSum(int[] array) {
        final int MODULUS = 1_000_000_007;
        int totalCount = 0, accumulatedSum = 0;
        int countOddSums = 0, countEvenSums = 1;
    
        for (int value : array) {
            accumulatedSum += value;
            if (accumulatedSum % 2 == 0) {
                totalCount += countOddSums;
                countEvenSums++;
            } else {
                totalCount += countEvenSums;
                countOddSums++;
            }
    
            totalCount %= MODULUS; 
        }
    
        return totalCount;
    }
}

The Java code provided outlines an efficient algorithm to determine the number of subarrays within an integer array that have an odd sum. The solution keeps track of the prefix sum of elements and uses this to determine whether the sum of elements from the start to any index is odd or even.

• The method countSubarraysWithOddSum(int[] array) initializes a modulus constant to prevent overflow issues.
• An integer totalCount is initialized to keep track of the number of subarrays with an odd sum.
• The integers accumulatedSum, countOddSums, and countEvenSums are used to track the running sum of array elements, and the counts of odd and even sums encountered respectively.
• Inside a loop that iterates through the array:
  • The accumulatedSum variable is updated by adding the current value.
  • Depending on whether accumulatedSum is odd or even, you increment totalCount appropriately using the counts of odd or even prefix sums found earlier.
  • The counts of odd and even sums are updated based on the current state of accumulatedSum.
  • The totalCount is taken modulo MODULUS to ensure it stays within the range of typical integer values and prevents overflow.
• The method finally returns the total count of subarrays with odd sums in the array.

This approach ensures that by leveraging prefix sums and maintaining a count of occurrences efficiently, the problem is solved with a time complexity that is linear with respect to the size of the input array, i.e., O(n).

class Solution:
    def countSubarrays(self, numbers: List[int]) -> int:
        modulus = 10**9 + 7
        total_subarrays = current_sum = 0
        evens_count = 1
        odds_count = 0
    
        for value in numbers:
            current_sum += value
            if current_sum % 2 == 0:
                total_subarrays += odds_count
                evens_count += 1
            else:
                total_subarrays += evens_count
                odds_count += 1
                
            total_subarrays %= modulus
    
        return total_subarrays

The provided Python3 code implements a solution for counting the number of subarrays in a given list of integers where the sum of the elements in the subarray is odd. Here's how the code accomplishes this task:

• Define a class Solution with a method countSubarrays.
• Initialize variables: modulus to handle the large output by taking modulus, total_subarrays to keep track of the count of subarrays with odd sum, current_sum to accumulate the sum of the elements while traversing, and evens_count and odds_count to track the number of even and odd sums encountered respectively.
• Iterate through each integer in the passed list:
  • Update current_sum with the current number.
  • If current_sum is even, increment the total_subarrays with the count of previously found odd sums because adding an even number to an odd sum makes it even and vice versa.
  • If current_sum is odd, increment the total_subarrays with the count of even sums.
  • Afterwards, update the count of even or odd sums as necessary.
  • Reduce total_subarrays using modulus operation to ensure it does not go beyond the set limit and to handle large numbers efficiently.
• Return the total_subarrays.

This method efficiently counts subarrays with odd sums using the properties of even and odd arithmetic, ensuring optimal performance for large datasets by managing the sum accumulations and maintaining the data within a manageable numeric range using modulo operation. The choice of the algorithm ensures that each element is only processed once, achieving O(n) time complexity.