1524. Number of Sub-arrays With Odd Sum - Explanation

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        n, res = len(arr), 0
        mod = int(1e9 + 7)

        for i in range(n):
            curSum = 0
            for j in range(i, n):
                curSum += arr[j]
                if curSum % 2:
                    res = (res + 1) % mod

        return res

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        mod = 10**9 + 7
        n = len(arr)
        memo = {}

        def dp(i: int, parity: int) -> int:
            if i == n:
                return 0

            if (i, parity) in memo:
                return memo[(i, parity)]

            new_parity = (parity + arr[i]) % 2
            res = new_parity + dp(i + 1, new_parity)
            memo[(i, parity)] = res % mod
            return memo[(i, parity)]

        ans = 0
        for i in range(n):
            ans = (ans + dp(i, 0)) % mod

        return ans

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        mod = 10**9 + 7
        dp = [[0] * 2 for _ in range(n + 1)]

        for i in range(n - 1, -1, -1):
            for parity in range(2):
                new_parity = (parity + arr[i]) % 2
                dp[i][parity] = (new_parity + dp[i + 1][new_parity]) % mod

        res = 0
        for i in range(n):
            res = (res + dp[i][0]) % mod
        return res

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        cur_sum = odd_cnt = even_cnt = res = 0
        MOD = 10**9 + 7

        for n in arr:
            cur_sum += n
            if cur_sum % 2:
                res = (res + 1 + even_cnt) % MOD
                odd_cnt += 1
            else:
                res = (res + odd_cnt) % MOD
                even_cnt += 1

        return res

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        count = [1, 0]
        prefix = res = 0
        MOD = 10**9 + 7

        for num in arr:
            prefix = (prefix + num) % 2
            res = (res + count[1 - prefix]) % MOD
            count[prefix] += 1

        return res