Is Number of Sub-arrays With Odd Sum easy or hard?

The problem is rated Medium because the brute force idea is straightforward but the optimal solution requires recognizing a prefix sum parity pattern. Once the odd-even prefix relationship is identified, the algorithm becomes a simple O(n) counting pass.

Number of Sub-arrays With Odd Sum Python/Java solution

In Python or Java, compute a running prefix sum and track parity using sum % 2. Maintain two variables counting even and odd prefixes and update the answer accordingly during iteration. The implementation is short and runs in O(n) time with constant space.

How to solve Number of Sub-arrays With Odd Sum in O(n)?

Maintain a running prefix sum and track whether it is even or odd. Keep two counters: number of even prefixes and number of odd prefixes seen so far. If the current prefix is odd, add the count of even prefixes to the answer; if it is even, add the count of odd prefixes. Update the prefix counters as you iterate through the array.

What is the best approach for Number of Sub-arrays With Odd Sum?

The optimal approach uses prefix sum parity counting. Track how many prefix sums are even and odd while iterating through the array. An odd subarray occurs whenever the current prefix parity differs from a previous prefix parity. This method runs in O(n) time and uses O(1) extra space.

Is Number of Sub-arrays With Odd Sum asked at Google/Amazon/Meta?

Variants of prefix sum parity problems appear frequently in interviews at companies like Amazon, Google, and Meta. Interviewers use them to evaluate understanding of prefix sums, parity properties, and how to transform a quadratic enumeration into a linear counting problem.

What data structure is used in Number of Sub-arrays With Odd Sum?

The solution mainly relies on prefix sums and simple counters for odd and even parity states. No complex data structures are required—just integer variables that track counts while iterating through the array.

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

The optimal solution runs in O(n) time because the array is scanned once while maintaining counts of even and odd prefix sums. A brute force approach that checks every subarray takes O(n^2) time, which is significantly slower for large inputs.

1524. Number of Sub-arrays With Odd Sum - Practice Online

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⁹ + 7.

Example 1:

Input: arr = [1,3,5]
Output: 4
Explanation: 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
Explanation: 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

Constraints:

1 <= arr.length <= 10⁵
1 <= arr[i] <= 100