#1524

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Number of Sub-arrays With Odd Sum

Count the number of subarrays with an odd sum using dynamic programming and prefix sum techniques.

array math dynamic programming prefix sum

Problem Statement

Given an array of integers, return the number of subarrays that have an odd sum. The result should be computed modulo 10^9 + 7.

A subarray is any contiguous portion of the array. The key challenge is to efficiently count subarrays with odd sums using dynamic programming and prefix sums.

Examples

Example 1

Input: arr = [1,3,5]

Output: 4

All subarrays are [[1],[1,3],[1,3,5],[3],[3,5],[5]] All sub-arrays sum are [1,4,9,3,8,5]. Odd sums are [1,9,3,5] so the answer is 4.

Example 2

Input: arr = [2,4,6]

Output: 0

All subarrays are [[2],[2,4],[2,4,6],[4],[4,6],[6]] All sub-arrays sum are [2,6,12,4,10,6]. All sub-arrays have even sum and the answer is 0.

Example 3

Input: arr = [1,2,3,4,5,6,7]

Output: 16

Example details omitted.

Constraints

1 <= arr.length <= 105
1 <= arr[i] <= 100

Solution Approach

Prefix Sum and Parity Count

Use a prefix sum to track the cumulative sum as you iterate through the array. Maintain two counts: one for even sums and one for odd sums. As you move through the array, check if the current prefix sum has been seen before and update the odd/even sum counts accordingly.

State Transition Dynamic Programming

Each time you encounter a new prefix sum, you transition from the previous state based on the parity (odd/even) of the sum. This dynamic programming approach allows you to calculate the number of subarrays with an odd sum in linear time.

Modulo Operations for Large Numbers

Since the result can be large, use modulo 10^9 + 7 to ensure that the answer fits within the required constraints. This is necessary to avoid overflow and to keep the calculations manageable.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity is O(n) because the algorithm processes each element in the array exactly once. The space complexity is O(1) since we are only maintaining a constant amount of state information (the counts of odd and even sums).

What Interviewers Usually Probe

Candidate shows familiarity with prefix sum techniques.
Candidate demonstrates understanding of dynamic programming state transitions.
Candidate correctly applies modulo operations to manage large numbers.

Common Pitfalls or Variants

Common pitfalls

Incorrectly updating the odd/even sum counts, leading to wrong results.
Overcomplicating the problem by attempting a brute-force solution with nested loops.
Failing to apply modulo 10^9 + 7, causing overflow issues.

Follow-up variants

Modify the problem to return subarrays with even sums.
Adapt the problem to count subarrays with sums divisible by a given number.
Consider variations with different data types (e.g., floating-point numbers).

FAQ

How can I solve the 'Number of Sub-arrays With Odd Sum' problem?

Use dynamic programming with prefix sums to track the cumulative sum and count the odd and even subarrays efficiently.

What is the optimal time complexity for this problem?

The optimal time complexity is O(n), where n is the length of the array.

Why is the modulo 10^9 + 7 used in this problem?

It is used to prevent overflow by keeping the result within manageable limits.

What is the key pattern used in this problem?

The key pattern is state transition dynamic programming, specifically using prefix sums and parity tracking.

What are some common pitfalls when solving this problem?

Common pitfalls include incorrect updates of the odd/even sum counts, failing to use modulo operations, and overcomplicating the solution.

terminal

Solution

Solution 1: Prefix Sum + Counter

We define an array $\textit{cnt}$ of length 2 as a counter, where $\textit{cnt}[0]$ and $\textit{cnt}[1]$ represent the number of subarrays with even and odd prefix sums, respectively. Initially, $\textit{cnt}[0] = 1$ and $\textit{cnt}[1] = 0$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        mod = 10**9 + 7
        cnt = [1, 0]
        ans = s = 0
        for x in arr:
            s += x
            ans = (ans + cnt[s & 1 ^ 1]) % mod
            cnt[s & 1] += 1
        return ans

Continue Practicing

#1872 stone game viii #1140 stone game ii #1563 stone game v