How do you solve Number of Sub-arrays With Odd Sum on LeetCode?

Number of Sub-arrays With Odd Sum (LeetCode #1524) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Subarrays with odd sums can be efficiently counted using prefix sums.

What is the time complexity of Number of Sub-arrays With Odd Sum?

The optimal solution for Number of Sub-arrays With Odd Sum runs in O(n) time and uses O(1) space. The complexity is O(n) because we only make a single pass through the array, maintaining a constant amount of additional space.

What is the brute force solution for Number of Sub-arrays With Odd Sum?

The brute force approach for Number of Sub-arrays With Odd Sum is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking every possible subarray and calculating its sum to see if it's odd. This is straightforward but inefficient for larger arrays. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Number of Sub-arrays With Odd Sum?

Number of Sub-arrays With Odd Sum uses the following concepts: Array, Math, Dynamic Programming, Prefix Sum. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Number of Sub-arrays With Odd Sum?

Always think about how to reduce the problem size — can you use prefix sums? Explain your thought process clearly, especially when transitioning from brute force to optimal solutions. Practice identifying patterns in problems, such as odd/even relationships.

What are common mistakes when solving Number of Sub-arrays With Odd Sum?

Forgetting to take modulo 10^9 + 7 at the end. Not considering the initial even prefix sum (0) when starting the count.

#1524

Number of Sub-arrays With Odd Sum

Medium

ArrayMathDynamic ProgrammingPrefix SumHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

We can use prefix sums to track the count of even and odd sums as we iterate through the array. This allows us to efficiently count subarrays with odd sums without explicitly calculating each subarray's sum.

⚙️

Algorithm

5 steps

1Step 1: Initialize counters for odd and even prefix sums.
2Step 2: Iterate through the array and maintain a running sum.
3Step 3: For each element, check if the running sum is odd or even.
4Step 4: If the sum is odd, add the count of even prefix sums to the result (as they can form odd-sum subarrays). If the sum is even, add the count of odd prefix sums.
5Step 5: Update the respective count of odd/even prefix sums.

solution.py16 lines

1# Full working Python code
2
3def numOfSubarrays(arr):
4    odd_count = 0
5    even_count = 1  # We start with one even prefix sum (0)
6    current_sum = 0
7    result = 0
8    for num in arr:
9        current_sum += num
10        if current_sum % 2 != 0:
11            result += even_count
12            odd_count += 1
13        else:
14            result += odd_count
15            even_count += 1
16    return result % (10**9 + 7)

ℹ

Complexity note: The complexity is O(n) because we only make a single pass through the array, maintaining a constant amount of additional space.

1Subarrays with odd sums can be efficiently counted using prefix sums.
2The relationship between odd and even sums allows us to use counts instead of explicit sums.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.