Number of Sub-arrays With Odd Sum

Leetcode Problem:

• Number of Sub-arrays With Odd Sum

Summary

• Find the number of subarrays with an odd sum in a given array of integers.

Approach

• The solution uses a prefix sum approach to keep track of the current sum of the subarray
• It also uses two counters, evenCount and oddCount, to keep track of the number of subarrays with even and odd sums respectively
• The time complexity is O(n) where n is the size of the array.

Complexity

• O(n)

Explanation

• The solution iterates over the array and for each element, it checks if the prefix sum is odd or even
• If it's odd, it increments the oddCount and adds the evenCount to the answer
• If it's even, it increments the evenCount and adds the oddCount to the answer
• The answer is then taken modulo MOD to prevent overflow
• The solution returns the final answer.

Solution Code:

class Solution {
public:
    #define MOD 1000000007
    int numOfSubarrays(vector& arr) {
        
        long long prefixSum = 0;
        int evenCount = 1;
        int oddCount = 0;
        int ans = 0;
        for(int i = 0 ; i < arr.size(); i++){
            prefixSum += arr[i];

            if(prefixSum & 1){
                oddCount++;
                ans += evenCount;
            } else{
                evenCount++;
                ans += oddCount;
            }
            ans %= MOD;
        }
        return ans;
    }
};