Leetcode 1524. Number of Sub-arrays With Odd Sum

Table of Contents

This is the daily question of leetcode in 2025-02-25.

Problem Description
#

Given an array of integers arr, return the number of subarrays with an odd sum.

Since the answer can be very large, return it modulo $10^9 + 7$.

Solution - Naive DP
#

Define dp[i][j] to represent the parity (odd or even) of the sum of the subarray from index $i$ to $j$. Specifically, dp[i][j] = true if the sum is odd and false otherwise.
Count the number of true values in dp and return the count modulo $10^9+7$.
Note that dp[i][j] is equal to true if and only if arr[j] is odd and dp[i][j-1] is even, or, arr[j] is even and dp[i][j-1] is odd.

Code
#

class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        const int MOD = 1e9 + 7;
        int n = arr.size();
        int result = 0;
        vector<vector<bool>> dp(n, vector<bool>(n, false));

        for(int i = 0; i < n; i++){
            if (arr[i] % 2 == 1){
                dp[i][i] = true;
                result = (result + 1) % MOD;
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if ((dp[i][j-1] == true && (arr[j] % 2 == 0)) || (dp[i][j-1] == false && (arr[j] % 2 == 1))){
                    dp[i][j] = true;
                    result = (result + 1) % MOD;
                }
            }
        }
        return result;
    }
};

Time complexity: $O(n^2)$ and will TLE in this question
Space complexity: $O(n^2)$

Solution - DP
#

We define dpEven[i] as the number of subarrays with an even sum that end at index $i$.

Similarly, dpOdd[i] represents the number of subarrays with an odd sum that end at index $i$.
If arr[i] is odd, we update dpOdd[i] as dpEven[i-1] + 1. This is because the only ways to form an odd-sum subarray ending at index $i$ are:
- Extending an even-sum subarray ending at index $i−1$ by including arr[i], or
- Taking arr[i] alone as a single-element subarray.
Likewise, we update dpEven[i] as dpOdd[i-1], since an even-sum subarray ending at index $i$ must be formed by extending an odd-sum subarray ending at index $i−1$ with arr[i].

The update rule follows a similar pattern if arr[i] is even.
Finally, summing up all dpOdd[i] values gives the total number of subarrays with an odd sum, which is our answer.

Code
#

class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        const int MOD = 1e9 + 7;
        int n = arr.size();
        vector<int> dpEven(n, 0);
        vector<int> dpOdd(n, 0);
        dpEven[0] = (arr[0] % 2 == 1) ? 0: 1;
        dpOdd[0] = (arr[0] % 2 == 1) ? 1: 0;
        for(int i = 1; i < n; i++){
            if(arr[i] % 2 == 1){
                dpOdd[i] = (dpEven[i-1] + 1) % MOD;
                dpEven[i] = (dpOdd[i-1]) % MOD;
            }
            else{
                dpOdd[i] = (dpOdd[i-1]) % MOD;
                dpEven[i] = (dpEven[i-1] + 1) % MOD;
            }
        }
        int result = 0;
        for(int i = 0; i < n; i++){
            result = (result + dpOdd[i]) % MOD;
        }
        return result;
    }
};

Time complexity: $O(n)$
Space complexity: $O(n)$

Solution - Prefix Sum
#

The sum of a subarray from index $i$ to index $j$ can be computed as: $$ \text{sum}(i, j) = \text{prefixSum}(j) - \text{prefixSum}(i-1) $$ This sum is odd if and only if the parity (odd/even status) of prefixSum(j) differs from prefixSum(i-1).
Based on this observation, we keep track of two values:

oddSum: The number of prefix sums that are odd before index $j$.
evenSum: The number of prefix sums that are even before index $j$.

If prefixSum of $j$ is odd, the number of subarrays ending at the current index $j$ with an odd sum is equal to evenSum, since an odd subarray is formed by subtracting an even prefix sum. Similar pattern if prefixSum of $j$ is even.

Code
#

class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        const int MOD = 1e9 + 7;
        int n = arr.size();
        int prefixSum = 0;
        int oddSum = 0; // num of odd prefixSum
        int evenSum = 1; //because 0 is even
        int result = 0;
        for(int num : arr){
            prefixSum += num;
            if (prefixSum%2 == 1){
                result += evenSum;
                oddSum++;
            }
            else{
                result += oddSum;
                evenSum++;
            }
            result %= MOD;
        }
        return result;
    }
};

Time complexity: $O(n)$
Space complexity: $O(1)$