1524. Number Of Subarrays With Odd Sum

Problem Statement in English

You’re given a list of integers arr. Your task is to find the number of odd sums of subarrays of arr.

Approach

You can easily brute force this. However, the constraints force you to find something more efficient.

The idea here is to simulate the process of generating the subarrays. We can do this by using prefix sums.

We can find the number of odd sum subarrays ending at the current index by using some math:

• $odd - even = odd$
• $even - odd = odd$

So, looking at the current sum…if we know the number of past subarrays with odd and even sums, we can easily calculate the number of odd sum subarrays ending at the current index.

And that’s it! Check out the code now.

Solution in Python

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        modulo = 1_000_000_007
        prefix_sums = [arr[0]]

        for num in arr[1:]:
            prefix_sums.append(prefix_sums[-1] + num)

        odd_sums = 0
        even_sums = 0
        res = 0

        for i in range(len(prefix_sums)):
            val = prefix_sums[i]

            # odd - even = odd
            if val % 2:
                res += 1
                res += even_sums
                # update odd sum count
                odd_sums += 1

            # even - odd = odd
            else:
                res += odd_sums
                # udpate even sum count
                even_sums += 1

        return res % modulo
        

Complexity

• Time: $O(n)$
  Since we are iterating through the array once, the time complexity is $O(n)$.

• Space: $O(n)$
  Since we calculate the prefix sums, the space complexity is $O(n)$.

However, we can optimize this to $O(1)$ space complexity by using two variables to keep track of the odd and even sums.

Mistakes I Made

I had to look this one up :(

And we are done.