1524. Number of Sub-arrays With Odd Sum - Explanation

Prerequisites

Before attempting this problem, you should be comfortable with:

Prefix Sum - Computing cumulative sums to determine subarray sums in constant time
Parity (Odd/Even) Properties - Understanding that odd minus even equals odd, and even minus odd equals odd
Dynamic Programming - Breaking down problems into overlapping subproblems with memoization or tabulation
Modular Arithmetic - Applying modulo operations to prevent integer overflow in counting problems

1. Brute Force

Intuition

For each possible subarray, compute its sum and check if it is odd. We try every starting index and extend to every possible ending index, accumulating the sum incrementally.

Algorithm

For each starting index i, initialize a running sum.
Extend the subarray by adding elements one at a time up to index n-1.
After each addition, check if the current sum is odd and increment res if so.
Return the total count modulo 10^9 + 7.

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        n, res = len(arr), 0
        mod = int(1e9 + 7)

        for i in range(n):
            curSum = 0
            for j in range(i, n):
                curSum += arr[j]
                if curSum % 2:
                    res = (res + 1) % mod

        return res

public class Solution {
    public int numOfSubarrays(int[] arr) {
        int n = arr.length, res = 0;
        int mod = (int)1e9 + 7;

        for (int i = 0; i < n; i++) {
            int curSum = 0;
            for (int j = i; j < n; j++) {
                curSum += arr[j];
                if (curSum % 2 != 0) {
                    res = (res + 1) % mod;
                }
            }
        }

        return res;
    }
}

class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        int n = arr.size(), res = 0;
        int mod = 1e9 + 7;

        for (int i = 0; i < n; i++) {
            int curSum = 0;
            for (int j = i; j < n; j++) {
                curSum += arr[j];
                if (curSum % 2 != 0) {
                    res = (res + 1) % mod;
                }
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} arr
     * @return {number}
     */
    numOfSubarrays(arr) {
        const n = arr.length;
        let res = 0;
        const mod = 1e9 + 7;

        for (let i = 0; i < n; i++) {
            let curSum = 0;
            for (let j = i; j < n; j++) {
                curSum += arr[j];
                if (curSum % 2 !== 0) {
                    res = (res + 1) % mod;
                }
            }
        }

        return res;
    }
}

public class Solution {
    public int NumOfSubarrays(int[] arr) {
        int n = arr.Length, res = 0;
        int mod = (int)1e9 + 7;

        for (int i = 0; i < n; i++) {
            int curSum = 0;
            for (int j = i; j < n; j++) {
                curSum += arr[j];
                if (curSum % 2 != 0) {
                    res = (res + 1) % mod;
                }
            }
        }

        return res;
    }
}

func numOfSubarrays(arr []int) int {
    n := len(arr)
    res := 0
    mod := int(1e9 + 7)

    for i := 0; i < n; i++ {
        curSum := 0
        for j := i; j < n; j++ {
            curSum += arr[j]
            if curSum%2 != 0 {
                res = (res + 1) % mod
            }
        }
    }

    return res
}

class Solution {
    fun numOfSubarrays(arr: IntArray): Int {
        val n = arr.size
        var res = 0
        val mod = 1_000_000_007

        for (i in 0 until n) {
            var curSum = 0
            for (j in i until n) {
                curSum += arr[j]
                if (curSum % 2 != 0) {
                    res = (res + 1) % mod
                }
            }
        }

        return res
    }
}

class Solution {
    func numOfSubarrays(_ arr: [Int]) -> Int {
        let n = arr.count
        var res = 0
        let mod = 1_000_000_007

        for i in 0..<n {
            var curSum = 0
            for j in i..<n {
                curSum += arr[j]
                if curSum % 2 != 0 {
                    res = (res + 1) % mod
                }
            }
        }

        return res
    }
}

Time & Space Complexity

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

2. Dynamic Programming (Top-Down)

Intuition

We use memoization to count subarrays ending at each position. For a subarray starting at index i, the parity of its sum depends on the running parity as we extend rightward. By caching results for each (index, parity) state, we avoid redundant calculations.

Algorithm

Define dfs(i, parity) returning the count of odd-sum subarrays starting at index i with the given running parity.
At each step, update the parity by adding the current element modulo 2.
Add 1 to the count if the new parity is odd, then recurse to the next index.
Sum up dfs(i, 0) for all starting indices to get the total.

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        mod = 10**9 + 7
        n = len(arr)
        memo = {}

        def dp(i: int, parity: int) -> int:
            if i == n:
                return 0

            if (i, parity) in memo:
                return memo[(i, parity)]

            new_parity = (parity + arr[i]) % 2
            res = new_parity + dp(i + 1, new_parity)
            memo[(i, parity)] = res % mod
            return memo[(i, parity)]

        ans = 0
        for i in range(n):
            ans = (ans + dp(i, 0)) % mod

        return ans

public class Solution {
    int[][] memo;
    int[] arr;
    int mod = (int)1e9 + 7;

    public int numOfSubarrays(int[] arr) {
        int n = arr.length;
        this.arr = arr;
        memo = new int[n][2];
        for (int i = 0; i < n; i++) {
            memo[i][0] = -1;
            memo[i][1] = -1;
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            res = (res + dp(i, 0)) % mod;
        }
        return res;
    }

    private int dp(int i, int parity) {
        if (i == arr.length) return 0;
        if (memo[i][parity] != -1) return memo[i][parity];

        int newParity = (parity + arr[i]) % 2;
        int res = newParity + dp(i + 1, newParity);
        return memo[i][parity] = res % mod;
    }
}

class Solution {
public:
    int mod = 1e9 + 7;
    vector<vector<int>> memo;
    vector<int> arr;

    int numOfSubarrays(vector<int>& arr) {
        this->arr = arr;
        int n = arr.size();
        memo.assign(n, vector<int>(2, -1));

        int res = 0;
        for (int i = 0; i < n; i++) {
            res = (res + dp(i, 0)) % mod;
        }
        return res;
    }

    int dp(int i, int parity) {
        if (i == arr.size()) return 0;
        if (memo[i][parity] != -1) return memo[i][parity];

        int newParity = (parity + arr[i]) % 2;
        int res = newParity + dp(i + 1, newParity);
        return memo[i][parity] = res % mod;
    }
};

class Solution {
    /**
     * @param {number[]} arr
     * @return {number}
     */
    numOfSubarrays(arr) {
        const mod = 1e9 + 7;
        const n = arr.length;
        const memo = Array.from({ length: n }, () => Array(2).fill(-1));

        const dp = (i, parity) => {
            if (i === n) return 0;
            if (memo[i][parity] !== -1) return memo[i][parity];

            const newParity = (parity + arr[i]) % 2;
            const res = newParity + dp(i + 1, newParity);
            return (memo[i][parity] = res % mod);
        };

        let res = 0;
        for (let i = 0; i < n; i++) {
            res = (res + dp(i, 0)) % mod;
        }

        return res;
    }
}

public class Solution {
    private int[][] memo;
    private int[] arr;
    private int mod = (int)1e9 + 7;

    public int NumOfSubarrays(int[] arr) {
        int n = arr.Length;
        this.arr = arr;
        memo = new int[n][];
        for (int i = 0; i < n; i++) {
            memo[i] = new int[] { -1, -1 };
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            res = (res + Dp(i, 0)) % mod;
        }
        return res;
    }

    private int Dp(int i, int parity) {
        if (i == arr.Length) return 0;
        if (memo[i][parity] != -1) return memo[i][parity];

        int newParity = (parity + arr[i]) % 2;
        int res = newParity + Dp(i + 1, newParity);
        return memo[i][parity] = res % mod;
    }
}

class Solution {
    fun numOfSubarrays(arr: IntArray): Int {
        val mod = 1_000_000_007
        val n = arr.size
        val memo = Array(n) { IntArray(2) { -1 } }

        fun dp(i: Int, parity: Int): Int {
            if (i == n) return 0
            if (memo[i][parity] != -1) return memo[i][parity]

            val newParity = (parity + arr[i]) % 2
            val res = newParity + dp(i + 1, newParity)
            memo[i][parity] = res % mod
            return memo[i][parity]
        }

        var res = 0
        for (i in 0 until n) {
            res = (res + dp(i, 0)) % mod
        }
        return res
    }
}

class Solution {
    func numOfSubarrays(_ arr: [Int]) -> Int {
        let mod = 1_000_000_007
        let n = arr.count
        var memo = [[Int]](repeating: [-1, -1], count: n)

        func dp(_ i: Int, _ parity: Int) -> Int {
            if i == n { return 0 }
            if memo[i][parity] != -1 { return memo[i][parity] }

            let newParity = (parity + arr[i]) % 2
            let res = newParity + dp(i + 1, newParity)
            memo[i][parity] = res % mod
            return memo[i][parity]
        }

        var res = 0
        for i in 0..<n {
            res = (res + dp(i, 0)) % mod
        }
        return res
    }
}

Time & Space Complexity

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

3. Dynamic Programming (Bottom-Up)

Intuition

We can convert the top-down approach to bottom-up by processing indices from right to left. For each position, we compute how many odd-sum subarrays can be formed starting there, given either even or odd running parity.

Algorithm

Create a 2D array dp[i][parity] representing counts from index i with given parity.
Iterate from the last index to the first.
For each parity, compute the new parity after including the current element and fill in the dp value.
Sum dp[i][0] for all indices to get the final answer.

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        mod = 10**9 + 7
        dp = [[0] * 2 for _ in range(n + 1)]

        for i in range(n - 1, -1, -1):
            for parity in range(2):
                new_parity = (parity + arr[i]) % 2
                dp[i][parity] = (new_parity + dp[i + 1][new_parity]) % mod

        res = 0
        for i in range(n):
            res = (res + dp[i][0]) % mod
        return res

public class Solution {
    public int numOfSubarrays(int[] arr) {
        int n = arr.length;
        int mod = (int)1e9 + 7;
        int[][] dp = new int[n + 1][2];

        for (int i = n - 1; i >= 0; i--) {
            for (int parity = 0; parity <= 1; parity++) {
                int newParity = (parity + arr[i]) % 2;
                dp[i][parity] = (newParity + dp[i + 1][newParity]) % mod;
            }
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            res = (res + dp[i][0]) % mod;
        }
        return res;
    }
}

class Solution {
    /**
     * @param {number[]} arr
     * @return {number}
     */
    numOfSubarrays(arr) {
        const n = arr.length;
        const mod = 1e9 + 7;
        const dp = Array.from({ length: n + 1 }, () => [0, 0]);

        for (let i = n - 1; i >= 0; i--) {
            for (let parity = 0; parity <= 1; parity++) {
                const newParity = (parity + arr[i]) % 2;
                dp[i][parity] = (newParity + dp[i + 1][newParity]) % mod;
            }
        }

        let res = 0;
        for (let i = 0; i < n; i++) {
            res = (res + dp[i][0]) % mod;
        }

        return res;
    }
}

public class Solution {
    public int NumOfSubarrays(int[] arr) {
        int n = arr.Length;
        int mod = (int)1e9 + 7;
        int[][] dp = new int[n + 1][];
        for (int i = 0; i <= n; i++) {
            dp[i] = new int[] { 0, 0 };
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int parity = 0; parity <= 1; parity++) {
                int newParity = (parity + arr[i]) % 2;
                dp[i][parity] = (newParity + dp[i + 1][newParity]) % mod;
            }
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            res = (res + dp[i][0]) % mod;
        }
        return res;
    }
}

class Solution {
    fun numOfSubarrays(arr: IntArray): Int {
        val n = arr.size
        val mod = 1_000_000_007
        val dp = Array(n + 1) { IntArray(2) }

        for (i in n - 1 downTo 0) {
            for (parity in 0..1) {
                val newParity = (parity + arr[i]) % 2
                dp[i][parity] = (newParity + dp[i + 1][newParity]) % mod
            }
        }

        var res = 0
        for (i in 0 until n) {
            res = (res + dp[i][0]) % mod
        }
        return res
    }
}

class Solution {
    func numOfSubarrays(_ arr: [Int]) -> Int {
        let n = arr.count
        let mod = 1_000_000_007
        var dp = [[Int]](repeating: [0, 0], count: n + 1)

        for i in stride(from: n - 1, through: 0, by: -1) {
            for parity in 0...1 {
                let newParity = (parity + arr[i]) % 2
                dp[i][parity] = (newParity + dp[i + 1][newParity]) % mod
            }
        }

        var res = 0
        for i in 0..<n {
            res = (res + dp[i][0]) % mod
        }
        return res
    }
}

Time & Space Complexity

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

4. Prefix Sum - I

Intuition

A subarray has an odd sum when its prefix sum parity differs from the prefix sum at its starting point. If the current prefix sum is odd, pairing it with any previous even prefix sum yields an odd subarray. We track counts of odd and even prefix sums seen so far.

Algorithm

Maintain counters for odd and even prefix sums encountered.
For each element, update the running prefix sum.
If the prefix sum is odd, add 1 (for the subarray from the start) plus the count of previous even prefix sums.
If even, add the count of previous odd prefix sums.
Update the appropriate counter and return res.

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        cur_sum = odd_cnt = even_cnt = res = 0
        MOD = 10**9 + 7

        for n in arr:
            cur_sum += n
            if cur_sum % 2:
                res = (res + 1 + even_cnt) % MOD
                odd_cnt += 1
            else:
                res = (res + odd_cnt) % MOD
                even_cnt += 1

        return res

public class Solution {
    public int numOfSubarrays(int[] arr) {
        int curSum = 0, oddCnt = 0, evenCnt = 0, res = 0;
        int MOD = (int)1e9 + 7;

        for (int n : arr) {
            curSum += n;
            if (curSum % 2 != 0) {
                res = (res + 1 + evenCnt) % MOD;
                oddCnt++;
            } else {
                res = (res + oddCnt) % MOD;
                evenCnt++;
            }
        }

        return res;
    }
}

class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        long long curSum = 0, oddCnt = 0, evenCnt = 0, res = 0;
        const int MOD = 1e9 + 7;

        for (int n : arr) {
            curSum += n;
            if (curSum % 2 != 0) {
                res = (res + 1 + evenCnt) % MOD;
                oddCnt++;
            } else {
                res = (res + oddCnt) % MOD;
                evenCnt++;
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} arr
     * @return {number}
     */
    numOfSubarrays(arr) {
        let curSum = 0,
            oddCnt = 0,
            evenCnt = 0,
            res = 0;
        const MOD = 1e9 + 7;

        for (let n of arr) {
            curSum += n;
            if (curSum % 2 !== 0) {
                res = (res + 1 + evenCnt) % MOD;
                oddCnt++;
            } else {
                res = (res + oddCnt) % MOD;
                evenCnt++;
            }
        }

        return res;
    }
}

public class Solution {
    public int NumOfSubarrays(int[] arr) {
        int curSum = 0, oddCnt = 0, evenCnt = 0, res = 0;
        int MOD = (int)1e9 + 7;

        foreach (int n in arr) {
            curSum += n;
            if (curSum % 2 != 0) {
                res = (res + 1 + evenCnt) % MOD;
                oddCnt++;
            } else {
                res = (res + oddCnt) % MOD;
                evenCnt++;
            }
        }

        return res;
    }
}

func numOfSubarrays(arr []int) int {
    curSum, oddCnt, evenCnt, res := 0, 0, 0, 0
    mod := int(1e9 + 7)

    for _, n := range arr {
        curSum += n
        if curSum%2 != 0 {
            res = (res + 1 + evenCnt) % mod
            oddCnt++
        } else {
            res = (res + oddCnt) % mod
            evenCnt++
        }
    }

    return res
}

class Solution {
    fun numOfSubarrays(arr: IntArray): Int {
        var curSum = 0
        var oddCnt = 0
        var evenCnt = 0
        var res = 0
        val mod = 1_000_000_007

        for (n in arr) {
            curSum += n
            if (curSum % 2 != 0) {
                res = (res + 1 + evenCnt) % mod
                oddCnt++
            } else {
                res = (res + oddCnt) % mod
                evenCnt++
            }
        }

        return res
    }
}

class Solution {
    func numOfSubarrays(_ arr: [Int]) -> Int {
        var curSum = 0, oddCnt = 0, evenCnt = 0, res = 0
        let mod = 1_000_000_007

        for n in arr {
            curSum += n
            if curSum % 2 != 0 {
                res = (res + 1 + evenCnt) % mod
                oddCnt += 1
            } else {
                res = (res + oddCnt) % mod
                evenCnt += 1
            }
        }

        return res
    }
}

Time & Space Complexity

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

5. Prefix Sum - II

Intuition

We only need to track the parity of the prefix sum (0 for even, 1 for odd). A count array of size 2 stores how many prefix sums of each parity we have seen. For each new element, we look up the count of the opposite parity to find valid subarrays.

Algorithm

Initialize count[0] = 1 to represent the empty prefix (sum 0, which is even).
For each element, toggle the prefix parity by adding the element modulo 2.
Add count[1 - prefix] to the result (subarrays ending here with odd sum).
Increment count[prefix] and continue.
Return the final result.

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        count = [1, 0]
        prefix = res = 0
        MOD = 10**9 + 7

        for num in arr:
            prefix = (prefix + num) % 2
            res = (res + count[1 - prefix]) % MOD
            count[prefix] += 1

        return res

public class Solution {
    public int numOfSubarrays(int[] arr) {
        int[] count = {1, 0};
        int prefix = 0, res = 0;
        int MOD = (int)1e9 + 7;

        for (int num : arr) {
            prefix = (prefix + num) % 2;
            res = (res + count[1 - prefix]) % MOD;
            count[prefix]++;
        }

        return res;
    }
}

class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        int count[2] = {1, 0};
        int prefix = 0, res = 0;
        const int MOD = 1e9 + 7;

        for (int num : arr) {
            prefix = (prefix + num) % 2;
            res = (res + count[1 - prefix]) % MOD;
            count[prefix]++;
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} arr
     * @return {number}
     */
    numOfSubarrays(arr) {
        const count = [1, 0];
        let prefix = 0,
            res = 0;
        const MOD = 1e9 + 7;

        for (const num of arr) {
            prefix = (prefix + num) % 2;
            res = (res + count[1 - prefix]) % MOD;
            count[prefix]++;
        }

        return res;
    }
}

public class Solution {
    public int NumOfSubarrays(int[] arr) {
        int[] count = { 1, 0 };
        int prefix = 0, res = 0;
        int MOD = (int)1e9 + 7;

        foreach (int num in arr) {
            prefix = (prefix + num) % 2;
            res = (res + count[1 - prefix]) % MOD;
            count[prefix]++;
        }

        return res;
    }
}

func numOfSubarrays(arr []int) int {
    count := []int{1, 0}
    prefix, res := 0, 0
    mod := int(1e9 + 7)

    for _, num := range arr {
        prefix = (prefix + num) % 2
        res = (res + count[1-prefix]) % mod
        count[prefix]++
    }

    return res
}

class Solution {
    fun numOfSubarrays(arr: IntArray): Int {
        val count = intArrayOf(1, 0)
        var prefix = 0
        var res = 0
        val mod = 1_000_000_007

        for (num in arr) {
            prefix = (prefix + num) % 2
            res = (res + count[1 - prefix]) % mod
            count[prefix]++
        }

        return res
    }
}

class Solution {
    func numOfSubarrays(_ arr: [Int]) -> Int {
        var count = [1, 0]
        var prefix = 0
        var res = 0
        let mod = 1_000_000_007

        for num in arr {
            prefix = (prefix + num) % 2
            res = (res + count[1 - prefix]) % mod
            count[prefix] += 1
        }

        return res
    }
}

Time & Space Complexity

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

Common Pitfalls

Forgetting to Initialize Even Count

When using the prefix sum approach, the empty prefix (sum of zero elements) has an even sum. If you forget to initialize count[0] = 1 or evenCnt = 0 with proper handling, you will miss subarrays that start from index 0.

Confusing Parity Logic

The key insight is that odd - even = odd and even - odd = odd. Some programmers mistakenly check if the current prefix sum is odd and then add the count of odd prefix sums, when they should be adding the count of even prefix sums (since subtracting an even prefix from an odd prefix yields an odd subarray sum).

Not Applying Modulo Correctly

The result can grow very large, so modulo 10^9 + 7 must be applied. A common mistake is applying modulo only at the end instead of during each addition, which can cause integer overflow in languages without arbitrary precision integers.