Number Of Sub Arrays With Odd Sum

---

Intuition

• odd + odd = even
• even + even = even
• odd + even = odd
• Since you are checking subarrays, everything is contiguous (which smells like a prefix problem)
  • For each index, you can check all previous prefixes and count how many are odd or even based on the current count.
• To optimize, count the number of odd and even for each previous index (you can just count the odd count, which avoids having to sum it every time)

Complexity

Runtime

• Optimized Prefix Sum: $O(N)$
• Naive: $O(N^2)$

Space

• $O(N)$, since there is just one

Code

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        ps = arr.copy()
        odd_cnt = [0] * n
 
        for i in range(n):
            if i > 0:
                odd_cnt[i] += odd_cnt[i - 1]
                ps[i] = ps[i] + ps[i - 1]        
            if ps[i] % 2 == 1:
                odd_cnt[i] += 1
 
        res = 0
        if ps[0] % 2 == 1:
            res += 1
 
        for i in range(1, n):
            if ps[i] % 2 == 0:
                res += odd_cnt[i - 1]
            else:
                res += i - odd_cnt[i - 1] + 1
 
        return res % (10 ** 9 + 7)

TLE

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        ps = arr.copy()
        for i in range(1, len(arr)):
            ps[i] = ps[i] + ps[i - 1]
 
        res = 0
        for i in range(len(ps)):
            is_odd = False
            if ps[i] % 2 == 1:
                res += 1  # +1 for additional odd number
                is_odd = True
        
            for j in range(i):
                if is_odd:
                    if ps[j] % 2 == 0:
                        res += 1
                elif ps[j] % 2 == 1:  # Is even
                    res += 1
            
        return res

Notes

Boox

Cards

START Basic Front: Number Of Sub Arrays With Odd Sum Back: odd + odd, even + odd, even + even END

---

References

• Number Of Sub Arrays With Odd Sum
• ChatGPT